题目大意：

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

POJ1195的加强版

没记错的话上午这题还没有中文题目描述的说0.0 好迅速

首先这题看到W就知道二维树状数组挂了 看到M就发现离散化了也搞不了 0.0

这题似乎是CDQ分治被发现之后第二个解决的题目。。。不过只有会员才知道的世界，今天反应过来刷刷。。。

修改和询问放在一起分治，一个询问拆分成4个，树状数组处理，每层分治处理左区间中修改对右区间的询问即可

此外题目描述有误，S不是初值，是操作的编号，我还纳闷怎么没加初值就AC了0.0 所以S恒为0，不用管了

#include
  
   
#include
   
     #include
    
      #include
     
       #define M 2002002 using namespace std; struct abcd{ int x,y,num,pos,ans; abcd(){} abcd(int X,int Y,int Num); bool operator <(const abcd &y)const { return x < y.x; } }q[200200],nq[200200]; int num,w,n,ans; int c[M],tim[M],T; void update(int x,int y) { for(;x<=w;x+=x&-x) { if(tim[x]!=T) c[x]=0; tim[x]=T; c[x]+=y; } } int getans(int x) { int re=0; for(;x;x-=x&-x) if(tim[x]==T) re+=c[x]; return re; } bool cmp(const abcd &x,const abcd &y) { return x.pos < y.pos; } abcd :: abcd(int X,int Y,int Num) { x=X; y=Y; num=Num; pos=n; ans=0; } void CDQ(int l,int r) { int i,j,mid=l+r>>1; int l1=l,l2=mid+1; if(l==r) return ; for(i=l;i<=r;i++) { if(q[i].pos<=mid) nq[l1++]=q[i]; else nq[l2++]=q[i]; } memcpy( q+l , nq+l , sizeof(q[0])*(r-l+1) ); CDQ(l,mid); j=l;++T; for(i=mid+1;i<=r;i++) { for(;q[j].x<=q[i].x&&j<=mid;j++) if(q[j].num!=19980402) update(q[j].y,q[j].num); if(q[i].num==19980402) q[i].ans+=getans(q[i].y); } CDQ(mid+1,r); l1=l;l2=mid+1; for(i=l;i<=r;i++) { if(q[l1]
      
       r) nq[i]=q[l1++]; else nq[i]=q[l2++]; } memcpy( q+l , nq+l , sizeof(q[0])*(r-l+1) ); } int main() { int i,p,x,y,z,x1,y1,x2,y2; cin>>num>>w; while(scanf("%d",&p),p^3) { if(p==1) scanf("%d%d%d",&x,&y,&z),q[++n]=abcd(x,y,z); else { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); q[++n]=abcd(x1-1,y1-1,19980402); q[++n]=abcd(x1-1,y2,19980402); q[++n]=abcd(x2,y1-1,19980402); q[++n]=abcd(x2,y2,19980402); } } sort(q+1,q+n+1); CDQ(1,n); sort(q+1,q+n+1,cmp); for(i=1;i<=n;i++) if(q[i].num==19980402) { ans=0; ans+=q[i++].ans; ans-=q[i++].ans; ans-=q[i++].ans; ans+=q[i ].ans; printf("%d\n",ans); } }