题目
维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
Input
第一行两个整数,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:表示输入结束
Output
对于每个输入2,输出一行,即输入2的答案
Sample Input
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
代码
#include<cstdio> #include<algorithm> using namespace std; #define lowbit(x) ((x)&-(x)) #define ff() for(int i=l;i<=r;i++) struct data{int v,x,y,d,f,pos; bool operator <(const data& w)const{ if(x!=w.x)return x<w.x;if(y!=w.y)return y<w.y; return pos<w.pos;} }a[200005],tmp[200005]; int s,w,t[2000005],cnt,ans[200005]; int I(){int x=0,f=1;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1; for(;'0'<=c&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);return x*f;} inline void add(int y,int x){for(int i=y;i<=w;i+=lowbit(i)) t[i]+=x;} inline int query(int y){int ret=0; for(int i=y;i;i-=lowbit(i)) ret+=t[i]; return ret;} void CDQ(int l,int r){if(l==r)return; int mid=(l+r)>>1,t1=l-1,t2=mid; ff(){if(a[i].v<=mid&&!a[i].pos)add(a[i].y,a[i].d); if(a[i].v>mid&&a[i].pos)ans[a[i].pos]+=query(a[i].y)*a[i].f;} ff()if(a[i].v<=mid&&!a[i].pos)add(a[i].y,-a[i].d); ff()a[i].v<=mid?tmp[++t1]=a[i]:tmp[++t2]=a[i]; ff()a[i]=tmp[i];CDQ(l,mid);CDQ(mid+1,r);} int main(){s=I();w=I();int t,x,y,d,x1,x2,y1,y2; while(1){t=I(); if(t==1)x=I(),y=I(),d=I(),a[++cnt]=(data){cnt,x,y,d,1,0}; else if(t==2)x1=I(),y1=I(),x2=I(),y2=I(),++ans[0], a[++cnt]=(data){cnt,x1-1,y1-1,0,1,ans[0]}, a[++cnt]=(data){cnt,x2,y2,0,1,ans[0]}, a[++cnt]=(data){cnt,x1-1,y2,0,-1,ans[0]}, a[++cnt]=(data){cnt,x2,y1-1,0,-1,ans[0]}; else break;}sort(a+1,a+1+cnt);CDQ(1,cnt); for(int i=1;i<=ans[0];i++)printf("%d ",ans[i]); return 0;}