问题 1938 --墓碑吞噬者2

1938: 墓碑吞噬者2★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 104  解决: 53
[提交][状态][命题人:]

题目描述

有一片NM列的草地,第一列草皮的右边是你的家。起初草地上一块墓碑也没有。现在夜深了,草地上突然会冒出一些墓碑出来。疯狂的戴夫种植墓碑吞噬者来消除墓碑。一个墓碑吞噬者会立即吞噬一块墓碑,然后消失。戴夫可能手抖把墓碑吞噬者种植在没有墓碑的草皮上,此时吞噬者会直接消失。戴夫发现墓碑实在太多了,他需要统计一片区域内还有多少墓碑。注意,一块草皮上可以有多块墓碑。

输入

第一行3个整数N,MP1<=N,M<=1000,1<=P<=100000,表示草地有N行M列,有P次次操作。

接下来P行,每行一个操作,格式如下:

add x y            表示坐标为(x,y)的草皮冒出了一块墓碑

eat x y            表示放置了一个墓碑吞噬者在坐标为(x,y)的草皮上。

query x1 y1 x2 y2 戴夫想知道左上角为(x1,y1),右下角为(x2,y2)的矩形区域内一共有多少块墓碑

输出

对于每个询问query,输出一行,即墓碑的数量。

样例输入
Copy
3 3 8
add 2 2
add 2 3
add 3 2
query 1 1 2 3
eat 3 3
add 1 1
add 3 2
query 1 2 3 3
样例输出
Copy
2
4

提示

来源

[提交][状态]