维护一个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的答案

保证答案不会超过int范围

 1 #include<iostream> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<algorithm> 6 #define LL long long 7 using namespace std; 8 const int mxn=2000100; 9 inline int read(){10     int sum=0,flag=1;char ch=getchar();11     while(ch!=‘-‘&&(ch>‘9‘||ch<‘0‘))ch=getchar();12     if(ch==‘-‘){flag=-1;ch=getchar();}13     while(ch<=‘9‘&&ch>=‘0‘){sum=sum*10+ch-‘0‘;ch=getchar();}14     return sum*flag;15 }16 int n;17 int t[mxn];18 struct opt{19     int flag,ti;int x,y,a;int id;20 }a[mxn];21 int cnt=0,ict=0;22 LL ans[mxn];23 int cmp(opt a,opt b){24     return (a.x<b.x || (a.x==b.x && a.ti<b.ti));25 }26 inline void add(int x,int v){27     while(x<=n){t[x]+=v;x+=x&-x;}28 }29 inline int ask(int x){30     int res=0;31     while(x){res+=t[x];x-=x&-x;}32     return res;33 }34 opt p[mxn];35 void solve(int l,int r){36     if(l>=r)return;37     int mid=(l+r)>>1;38     int l1=l,l2=mid+1;39     for(int i=l;i<=r;i++){40         if(a[i].flag==1 && a[i].ti<=mid)add(a[i].y,a[i].a);41         else if(a[i].flag==2 && a[i].ti>mid) ans[a[i].id]+=ask(a[i].y)*a[i].a;42     }43     for(int i=l;i<=r;i++)if(a[i].flag==1 && a[i].ti<=mid)add(a[i].y,-a[i].a);44     for(int i=l;i<=r;i++){45         if(a[i].ti<=mid) p[l1++]=a[i];46         else p[l2++]=a[i];47     }48     for(int i=l;i<=r;i++)a[i]=p[i];49     solve(l,mid);solve(mid+1,r);50     return;51 }52 int main(){53     int i,j,S;54     S=read();n=read();55     int op,X1,Y1,X2,Y2,w;56     while(1){57         op=read();58         if(op==3)break;59         if(op==1){60             X1=read();Y1=read();w=read();61             a[++cnt].x=X1;a[cnt].y=Y1;a[cnt].a=w;a[cnt].flag=1;a[cnt].ti=cnt;62         }63         else{64             X1=read()-1;Y1=read()-1;X2=read();Y2=read();65             a[++cnt].x=X1;a[cnt].y=Y1;a[cnt].a=1;a[cnt].flag=2;a[cnt].ti=cnt;a[cnt].id=++ict;66             a[++cnt].x=X1;a[cnt].y=Y2;a[cnt].a=-1;a[cnt].flag=2;a[cnt].ti=cnt;a[cnt].id=ict;67             a[++cnt].x=X2;a[cnt].y=Y1;a[cnt].a=-1;a[cnt].flag=2;a[cnt].ti=cnt;a[cnt].id=ict;68             a[++cnt].x=X2;a[cnt].y=Y2;a[cnt].a=1;a[cnt].flag=2;a[cnt].ti=cnt;a[cnt].id=ict;69             ans[ict]=(X2-X1)*(Y2-Y1)*S;70         }71     }72     sort(a+1,a+cnt+1,cmp);73     solve(1,cnt);74     for(i=1;i<=ict;i++){75         printf("%lld\n",ans[i]);76     }77     return 0;78 }