题意：给出一个W*W的矩阵，有两个操作：1.对矩阵中的某一个点进行增加a的操作 2.询问矩阵中(x1,y1)为左下角(x2,y2)为右上角的矩阵包含的点权值和为多少
题解：首先，操作2可以分解为4个关于区间的查询如下图。
由于增加点权值的操作对其他操作互不影响，且可以离线，所以可以采用CDQ分治的离线做法。
对（L，R）的操作进行横坐标排序，对于插入操作按横坐标次序对操作时间处于（L，mid）操作按y坐标插入到树状数组中，对于查询操作按横坐标次序对操作时间处于（mid+1，R）的操作进行查询。
之后将树状数组中的操作还原以免对后续运算产生影响。
再将已经排好序的操作分为时间段（L，mid）与时间段（mid+1，R）的两个区间，分别继续进行以上操作，直到为一个元素。
由于每一层插入与查询总操作的时间为nlogw，一共需要进行logn轮，所以总的复杂度为nlognlogw，空间复杂度为nlogw
AC代码：
#include<stdio.h> #include<algorithm> using namespace std; struct node { int op,x,y; int t,id,A; node(){} node(int op,int x,int y,int t,int id,int A) { this->op=op; this->x=x; this->y=y; this->t=t; this->id=id; this->A=A; } }qu[800005],newq[800005]; int initnum,w; int c[2000005]; int ans[2000005]; int tot,top; bool cmp(node a,node b) { if(a.x==b.x&&a.y==b.y)return a.op<b.op; if(a.x==b.x)return a.y<b.y; return a.x<b.x; } int lowbit(int i) { return i&(-i); } void add(int i,int k) { while(i<=w) { c[i]+=k; i+=lowbit(i); } } int sum(int i) { int ans=0; while(i) { ans+=c[i]; i-=lowbit(i); } return ans; } void solve(int l,int r) { if(l==r)return ; int mid=l+r>>1; for(int i=l;i<=r;i++) { if(qu[i].op==1&&qu[i].t<=mid)add(qu[i].y,qu[i].A); if(qu[i].op==2&&qu[i].t>mid)ans[qu[i].id]+=sum(qu[i].y)*qu[i].A; } for(int i=l;i<=r;i++) if(qu[i].op==1&&qu[i].t<=mid)add(qu[i].y,-qu[i].A); int l1=l,l2=mid+1; for(int i=l;i<=r;i++) { if(qu[i].t>mid)newq[l2++]=qu[i]; if(qu[i].t<=mid)newq[l1++]=qu[i]; } for(int i=l;i<=r;i++) qu[i]=newq[i]; solve(l,mid); solve(mid+1,r); } int main() { scanf("%d%d",&initnum,&w); for(int i=1;i<=w;i++)add(i,initnum); for(;;) { int op,x,y,v; scanf("%d",&op); if(op==1) { scanf("%d%d%d",&x,&y,&v); qu[tot]=node(op,x,y,tot,0,v); tot++; } else if(op==2) { int x2,y2; scanf("%d%d%d%d",&x,&y,&x2,&y2); qu[tot]=node(op,x2,y2,tot,top,1); tot++; qu[tot]=node(op,x-1,y2,tot,top,-1); tot++; qu[tot]=node(op,x2,y-1,tot,top,-1); tot++; qu[tot]=node(op,x-1,y-1,tot,top,1); tot++;top++; } else break; } sort(qu,qu+tot,cmp); solve(0,tot-1); for(int i=0;i<top;i++) printf("%d\n",ans[i]); }