Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

03/8
19:52
cdq分治

[bzoj 2683] 简单题

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:

命令 参数限制 内容
1 x y A 1<=x,y<=N,A是正整数 将格子x,y里的数字加上A
2 x1 y1 x2 y2 1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和
3 终止程序

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入文件第一行一个正整数N。
接下来每行一个操作。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个2操作,输出一个对应的答案。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3
5

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1<=N<=500000,操作数不超过200000个,内存限制20M。
对于100%的数据,操作1中的A不超过2000。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

cdq分治,双倍经验,同bzoj1176

c++:

pascal:

 

[bzoj 2683] 简单题