网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
蝗灾
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | locust.in | 输出文件 | locust.out |
DESCRIPTION
C国国土辽阔,地大物博......但是最近却在闹蝗灾.....
我们可以把C国国土当成一个W×W的矩阵,你会收到一些诸如(X,Y,Z)的信息,代表(X,Y)这个点增多了
Z只蝗虫,而由于C国政府机关比较臃肿,为了批复消灭蝗虫的请求需要询问一大堆的问题......每个询问形如
(X1,Y1,X2,Y2),询问在(X1,Y1,X2,Y2)范围内有多少蝗虫(请注意询问不会改变区域内的蝗虫数),
你作为一个C国的程序员,需要编一个程序快速的回答所有的询问。
NOTICE
C国一开始没有蝗虫。
INPUT
输入文件的第一行包括一个整数W,代表C国国土的大小。第二行有一个整数N,表示事件数。接下来有N行表示N个事件,以(0 X Y Z)的形式或(1,X1,Y1,X2,Y2)的形式给出,分别代表蝗虫的增加和询问。
OUTPUT
对于每个询问输出一个整数表示需要的结果。
SAMPLE INPUT
locust.in
5
8
2 4 1 4 2
1 3 1 8
1 4 4 4
2 1 3 4 4
1 1 5 1
1 4 4 5
2 2 2 5 4
2 3 2 4 4
SAMPLE OUTPUT
locust.out
0
4
9
9
数据范围:
10%的数据满足W<=100,N<=100;
30%的数据满足W<=2000,N<=5000;
50%的数据满足W<=100000,N<=50000;
100%的数据满足W<=500000,N<=200000,每次蝗虫增加数不超过1000;
时间限制:
2s