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

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

对于每个输入2,输出一行,即输入2的答案

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int s,n,tr[N],cnt,tot,ans[N];

 struct query{

     int id,k,w,x,y;

     bool operator <(const query &a)const{

         if(a.id==id){

             if(a.x==x){

                 if(a.y==y){

                     return a.k>k;

                 }

                 else return a.y>y;

             }

             else return a.x>x;

         }

         else return a.id>id;

     }

 }q[N],c[N];

 bool pd(query a,query b){

     if(a.x==b.x){

         if(a.y==b.y){

             return a.k<b.k;

         }

         else return a.y<b.y;

     }

     else return a.x<b.x;

 }

 int lowbit(int x){

     return x&-x;

 }

 void add(int x,int w){

     for(int i=x;i<=n;i+=lowbit(i)){

         tr[i]+=w;

     }

 }

 int getsum(int x){

     int ans=;

     for(int i=x;i>=;i-=lowbit(i)){

         ans+=tr[i];

     }

     return ans;

 }

 void cdq(int l,int r){

     if(l==r)return;

     int mid=(l+r)>>;

     cdq(l,mid);cdq(mid+,r);

     int ll=l;int rl=mid+;int now=;

     while(ll<=mid&&rl<=r){

         if(pd(q[ll],q[rl])){

             if(q[ll].k==)add(q[ll].y,q[ll].w);

             c[++now]=q[ll++];

         }

         else{

             if(q[rl].k==)ans[q[rl].w]-=getsum(q[rl].y);

             else if(q[rl].k==)ans[q[rl].w]+=getsum(q[rl].y);

             c[++now]=q[rl++];

         }

     }

     while(ll<=mid){

         if(q[ll].k==)add(q[ll].y,q[ll].w);

         c[++now]=q[ll++];

     }

     while(rl<=r){

         if(q[rl].k==)ans[q[rl].w]-=getsum(q[rl].y);

         else if(q[rl].k==)ans[q[rl].w]+=getsum(q[rl].y);

         c[++now]=q[rl++];

     }

     for(int i=l;i<=mid;i++){

         if(q[i].k==)add(q[i].y,-q[i].w);

     }

     for(int i=l;i<=r;i++){

         q[i]=c[i-l+];

     }

 }

 int main(){

     scanf("%d%d",&s,&n);

     n+=;

     while(){

         int k;

         scanf("%d",&k);

         if(k==){

             int x,y,a;

             scanf("%d%d%d",&x,&y,&a);

             x+=;y+=;

             q[++cnt].x=x;q[cnt].y=y;

             q[cnt].id=cnt;q[cnt].k=;

             q[cnt].w=a;

         }

         else if(k==){

             int x1,y1,x2,y2;

             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

             x1+=;y1+=;x2+=;y2+=;

             q[++cnt].x=x2;q[cnt].y=y2;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=++tot;

             q[++cnt].x=x1-;q[cnt].y=y2;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=tot;

             q[++cnt].x=x2;q[cnt].y=y1-;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=tot;

             q[++cnt].x=x1-;q[cnt].y=y1-;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=tot;

         }

         else break;

     }

     sort(q+,q++cnt);

 //    for(int i=1;i<=cnt;i++){

 //        cout<<q[i].id<<" "<<q[i].x<<" "<<q[i].y<<" "<<q[i].k<<" "<<q[i].w<<endl;;

 //    }

     cdq(,cnt);

     for(int i=;i<=tot;i++){

         printf("%d\n",ans[i]);

     }

     return ;

 }