题目描述
摩尔瓦多的移动电话公司摩基亚（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，输出一个一行整数，即当前询问矩形内的用户数量。

输入输出样例
输入 #1复制
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
输出 #1复制
3
5
说明/提示
对于所有数据：

1<=W<=2000000
1<=X1<=X2<=W
1<=Y1<=Y2<=W
1<=x,y<=W
0<A<=10000
命令1不超过160000个。
命令2不超过10000个。

一道以时间以一维的cdq分治。应该不难想到。

这道题我们用cdq分治，求类似前缀和，一个查询，我们去用四个前缀和的查询，代替一个非前缀的查询，画画图就能想到。

然后这道题因为我们是求前缀和嘛，所以可能出现边界是0的情况，所以我们让整体加一即可，不然树状数组会死循环。

然后因为我们cdq时对x排序了，所以最后求答案时要返回去，对时间排序即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=2e5+10,M=2e6+10;
int d[M],n,tot,res[N];
struct node{
	int tm,x,y,cnt,id;
}t[N];
inline void add(int x,int v){
	for(int i=x;i<M;i+=lowbit(i))	d[i]+=v;	
}
inline int ask(int x){
	int res=0;	for(int i=x;i;i-=lowbit(i))	res+=d[i];	return res;
}
bool cmp(const node &s1,const node &s2){
	return (s1.x==s2.x)?(s1.y<s2.y):(s1.x<s2.x);
}
bool cmpt(const node &s1,const node &s2){
	return s1.tm<s2.tm;
}
void cdq(int l,int r){
	if(l==r)	return ;	int mid=l+r>>1;
	cdq(l,mid);	cdq(mid+1,r);
	sort(t+l,t+mid+1,cmp);	sort(t+mid+1,t+r+1,cmp);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&t[j].x<=t[i].x){
			if(t[j].id)	add(t[j].y,t[j].cnt);
			j++;
		}
		if(!t[i].id)	t[i].cnt+=ask(t[i].y);
	}
	for(int i=l;i<j;i++) if(t[i].id)	add(t[i].y,-t[i].cnt);
}
signed main(){
	scanf("%d %d",&n,&n);
	while(1){
		int op;	scanf("%d",&op);
		if(op==3)	break;
		if(op==1){
			int x,y,a;	scanf("%d %d %d",&x,&y,&a);	++x; ++y;
			t[++tot]={tot,x,y,a,1};
		}else{
			int x1,y1,x2,y2;	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			++x2;	++y2;
			t[++tot]={tot,x1,y1,0,0}; t[++tot]={tot,x2,y2,0,0};
			t[++tot]={tot,x1,y2,0,0}; t[++tot]={tot,x2,y1,0,0};
		}
	}
	cdq(1,tot);	sort(t+1,t+1+tot,cmpt);
	for(int i=1;i<=tot;i++){
		if(!t[i].id){
			printf("%d\n",t[i].cnt+t[i+1].cnt-t[i+2].cnt-t[i+3].cnt); i+=3;
		}
	}
	return 0;
}