【题目描述】
摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。
在定位系统中，世界被认为是一个W×W的正方形区域，由1×1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形，就有1<=x<=4,1<=y<=4（如图）: 
请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。
【输入格式】
有三种命令，意义如下：
| 命令 | 参数 | 意义 |
|---|---|---|
| 0 | W | 初始化一个全零矩阵。本命令仅开始时出现一次。 |
| 1 | x y A | 向方格(x,y)中添加A个用户。A是正整数。 |
| 2 | X1 Y1 X2 Y2 | 查询X1<=x<=X2，Y1<=y<=Y2所规定的矩形中的用户数量 |
| 3 | 无参数 | 结束程序。本命令仅结束时出现一次。 |
【输出格式】
对所有命令2，输出一个一行整数，即当前询问矩形内的用户数量。
【输入样例】
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
【输出样例】
3
5
【提示】
| 输入 | 输出 | 意义 |
|---|---|---|
| 0 4 | 大小为4×4的全零正方形 | |
| 1 2 3 3 | 向(2,3)方格加入3名用户 | |
| 2 1 1 3 3 | 查询矩形1<=x<=3,1<=y<=3内的用户数量 | |
| 3 | 查询结果 | |
| 1 2 2 2 | 向(2,2)方格加入2名用户 | |
| 2 2 2 3 4 | 查询矩形2<=x<=3,2<=y<=4内的用户数量 | |
| 5 | 查询结果 | |
| 3 | 终止程序 |
【数据规模】
1<=W<=2000000
1<=X1<=X2<=W
1<=Y1<=Y2<=W
1<=x,y<=W
0<A<=10000
命令1不超过160000个。
命令2不超过10000个。
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 800010
#define MAXL 2000010
struct Query
{
int x, y, val, pos, id, opt;
bool operator<(const Query a) const
{
if (x == a.x && y == a.y)
return opt < a.opt;
return x == a.x ? y < a.y : x < a.x;
}
} Ask[MAXN], tmp[MAXN];
int n, m, Ans[MAXN];
class BIT
{
public:
int _tree[MAXL];
BIT() { ; }
#define lowbit(_) ((_) & (-_))
void Update(int i, int val)
{
for (; i <= n; i += lowbit(i))
_tree[i] += val;
return;
}
int Query(int i)
{
int _ans = 0;
for (; i; i -= lowbit(i))
_ans += _tree[i];
return _ans;
}
} bit;
void add()
{
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
++Ans[0];
Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y1 - 1, Ask[m].val = 1, Ask[m].opt = 1;
Ask[++m].pos = Ans[0], Ask[m].x = x2, Ask[m].y = y2, Ask[m].val = 1, Ask[m].opt = 1;
Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y2, Ask[m].val = -1, Ask[m].opt = 1;
Ask[++m].pos = Ans[0], Ask[m].x = x2, Ask[m].y = y1 - 1, Ask[m].val = -1, Ask[m].opt = 1;
return;
}
void CDQ(int l, int r)
{
if (l == r)
return;
int mid = l + r >> 1, l1 = l, l2 = mid + 1;
for (int i = l; i <= r; i++)
{
if (Ask[i].id <= mid && !Ask[i].opt)
bit.Update(Ask[i].y, Ask[i].val);
if (Ask[i].id > mid && Ask[i].opt)
Ans[Ask[i].pos] += Ask[i].val * bit.Query(Ask[i].y);
}
for (int i = l; i <= r; i++)
if (Ask[i].id <= mid && !Ask[i].opt)
bit.Update(Ask[i].y, -Ask[i].val);
for (int i = l; i <= r; i++)
{
if (Ask[i].id <= mid)
tmp[l1++] = Ask[i];
else
tmp[l2++] = Ask[i];
}
for (int i = l; i <= r; i++)
Ask[i] = tmp[i];
CDQ(l, mid);
CDQ(mid + 1, r);
return;
}
int main()
{
int c;
freopen("mokia.in", "r", stdin);
freopen("mokia.out", "w", stdout);
scanf("%d%d", &c, &n);
while (1)
{
int op;
scanf("%d", &op);
if (op == 1)
{
++m;
scanf("%d%d%d", &Ask[m].x, &Ask[m].y, &Ask[m].val);
}
else if (op == 2)
{
add();
}
else
break;
}
for (int i = 1; i <= m; i++)
Ask[i].id = i;
sort(Ask + 1, Ask + m + 1);
CDQ(1, m);
for (int i = 1; i <= Ans[0]; i++)
printf("%d\n", Ans[i]);
}