题解：
cdq分治
编号当作第一位
行当作第二位
列当作第三位
然后cdq+树状数组
代码：
#include<bits/stdc++.h> const int N=1000005; using namespace std; int n,m,cnt,sum[N],pos[N],ans[N]; struct date{int op,x,y,v,id;}qs[N]; int comp(date x,date y){return x.x<y.x;} void add(int x,int y){for (int i=x;i<=n;i+=i&-i)sum[i]+=y;} int query(int x) { int temp=0; for (int i=x;i;i-=i&-i)temp+=sum[i]; return temp; } void solve(int l,int r) { if (l==r) return; int mid=(l+r)/2,temp=0; solve(l,mid);solve(mid+1,r); sort(qs+l,qs+mid+1,comp); sort(qs+mid+1,qs+r+1,comp); int i=l,j=mid+1; while (j<=r) { while (qs[i].op==2&&i<=mid) i++; while (qs[j].op==1&&j<=r) j++; if (i<=mid&&qs[i].x<=qs[j].x) add(qs[i].y,qs[i].v),i++,temp=i-1; else if (j<=r) ans[qs[j].id]+=query(qs[j].y),j++; } for (int t=l;t<=temp;t++) if (qs[t].op==1) add(qs[t].y,-qs[t].v); } int main() { memset(ans,0,sizeof(ans)); memset(sum,0,sizeof(sum)); int op,x1,x2,y1,y2; scanf("%d",&n),m=cnt=0; for (;;) { scanf("%d",&op); if (op==1) { qs[++m].op=op,qs[m].id=m; scanf("%d%d%d",&qs[m].x,&qs[m].y,&qs[m].v); } else { if (op==2) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); pos[++cnt]=m; qs[++m].op=op,qs[m].x=x1-1,qs[m].y=y1-1,qs[m].id=m; qs[++m].op=op,qs[m].x=x2,qs[m].y=y2,qs[m].id=m; qs[++m].op=op,qs[m].x=x1-1,qs[m].y=y2,qs[m].id=m; qs[++m].op=op,qs[m].x=x2,qs[m].y=y1-1,qs[m].id=m; } else break; } } solve(1,m); for (int i=1;i<=cnt;i++) printf("%d ",ans[pos[i]+1]+ans[pos[i]+2]-ans[pos[i]+3]-ans[pos[i]+4]); }