【题目描述】
摩尔瓦多的移动电话公司摩基亚（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个。
【来源】
Balkan Olypiad in Informatics 2007,Mokia
Solution
cdq分支模板题
#include <stdio.h>
#include <algorithm>
int w, C[2000010], ans[10010];
struct Que{
int x, y, v, tp, _id;
}q[200010];
bool cmp(Que a, Que b) {return a.x < b.x;}
inline void add(int i, int d){
for(; i <= w; i += i & (-i))
C[i] += d;
}
inline int sum(int i){
int res = 0;
for(; i; i -= i & (-i))
res += C[i];
return res;
}
void cdq(int l, int r){
if(l == r) return;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
std::sort(q + l, q + mid + 1, cmp);
std::sort(q + mid + 1, q + r + 1, cmp);
int j = l;
for(int i = mid + 1; i <= r; i++){
for(; j <= mid && q[j].x <= q[i].x; j++)
if(q[j].tp == 1) add(q[j].y, q[j].v);
if(q[i].tp == 2) ans[q[i]._id] += q[i].v * sum(q[i].y);
}
for(int i = l; i < j; i++)
if(q[i].tp == 1) add(q[i].y, -q[i].v);
}
int main(){
int op, a, b, c, d, id = 0, tot = 0;
freopen("mokia.in", "r", stdin), freopen("mokia.out", "w", stdout);
while(scanf("%d", &op) && op != 3){
if(op == 0)
scanf("%d", &w);
else if(op == 1){
scanf("%d%d%d", &a, &b, &c);
q[++id] = (Que) {a, b, c, 1, 0};
}
else{
++tot;
scanf("%d%d%d%d", &a, &b, &c, &d);
q[++id] = (Que) {a - 1, b - 1, 1, 2, tot};
q[++id] = (Que) {c, d, 1, 2, tot};
q[++id] = (Que) {a - 1, d, -1, 2, tot};
q[++id] = (Que) {c, b - 1, -1, 2, tot};
}
}
cdq(1, id);
for(int i = 1; i <= tot; i++)
printf("%d\n", ans[i]);
fclose(stdin), fclose(stdout);
return 0;
}