cdq分治妙啊
（被改过题面的）原题：
dydxh所出的题目是这样的：
有一个N*N矩阵，给出一系列的修改和询问，修改是这样的：将(x,y)中的数字加上k，而询问是这样的：求(x1,y1)到(x2,y2)这个子矩阵内所有数字的和。
虽然这么高级的数据结构题mzx这种菜逼当然不会，但是由于dydxh给mzx留了一条没有强制在线的生路，所以mzx决定挑战一下这道题。
1<=N<=500000,操作数不超过200000个,操作1中的k为正整数，且不超过2000
思路很妙，知道为什么要这样做但是感觉考场上想不出来QAQ
首先询问容斥成4个前缀和问题，设时间轴为z，问题就变成询问z<qz，x<qx，y<qy里面的数总和是多少
然后就跟数星星很像了，排序x，这样右边的x保证比左边的x大，cdq分治z，树状数组y
看网上的做法和我之前想的有点不一样，我之前想的是想归并排序那样从将右边的队头和左边的队头比较，小的出队，先递归，再计算
网上比较多的做法是，先计算，左边的修改给右边的查询贡献，然后把时间轴<=mid的放到mid左边，>mid的放到右边，再递归下一层
感觉第二种对于我来说更好理解吧，比较贴合cdq分治的本质，现在还不能理解这两种写法的联系
听闵神说递归的效率非常低？我和山神的递归2.2s，闵神迭代0.4s……
还需要想一下迭代的写法啊
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;
}
struct cdd{int x,y,z,v,mk;}a[]; int tp=;
int n;
int e[],lbt[];
cdd q[]; int hd=;
int ans[];
int t=;
void gtlbt(){for(int i=;i<=;++i)lbt[i]=i&-i;}
void mdf(int x,int y){while(x<=n) e[x]+=y,x+=lbt[x];}
int qr(int x){int bwl=; while(x) bwl+=e[x],x-=lbt[x]; return bwl;}
//int qr(int x){int bwl=0; while(x) bwl+=e[x],x-=lbt[x];}
void dfs(int l,int r){
if(l==r) return ;
int md=(l+r)>>;
for(int i=l;i<=r;++i){
if(!a[i].mk && a[i].z<=md) mdf(a[i].y,a[i].v);
else if(a[i].mk && a[i].z>md)
ans[a[i].v]+=a[i].mk*qr(a[i].y);
}
for(int i=l;i<=r;++i)if(!a[i].mk && a[i].z<=md) mdf(a[i].y,-a[i].v);
int t1=l,t2=md+;
for(int i=l;i<=r;++i) q[(a[i].z<=md?t1:t2)++]=a[i];
for(int i=l;i<=r;++i) a[i]=q[i];
dfs(l,md),dfs(md+,r);
}
bool cmp(cdd x,cdd y){return (x.x==y.x)?((x.z==y.z)?x.y<y.y:x.z<y.z):x.x<y.x;}
int main(){//freopen("ddd.in","r",stdin);
gtlbt();
cin>>n;
int mk,x,y,z,v;
while((mk=read())!=){
if(mk==) a[++tp].mk=,a[tp].x=read(),a[tp].y=read(),a[tp].v=read(),a[tp].z=tp;
else{
x=read(),y=read(),z=read(),v=read();
a[++tp].mk=,a[tp].x=z,a[tp].y=v,a[tp].z=tp,a[tp].v=++t;
a[++tp].mk=,a[tp].x=x-,a[tp].y=y-,a[tp].z=tp,a[tp].v=t;
a[++tp].mk=-,a[tp].x=z,a[tp].y=y-,a[tp].z=tp,a[tp].v=t;
a[++tp].mk=-,a[tp].x=x-,a[tp].y=v,a[tp].z=tp,a[tp].v=t;
}
}
sort(a+,a+tp+,cmp);
dfs(,tp);
for(int i=;i<=t;++i) printf("%d\n",ans[i]);
return ;
}