Description
维护一个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
HINT
保证答案不会超过int范围
#include<cstdio> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<algorithm> #include<iostream> #include<queue> #include<stack> #include<map> using namespace std; #define FOU(i,x,y) for(int i=x;i<=y;i++) #define FOD(i,x,y) for(int i=x;i>=y;i--) #define MEM(a,val) memset(a,val,sizeof(a)) #define PI acos(-1.0) const double EXP = 1e-9; typedef long long ll; typedef unsigned long long ull; const int INF = 0x3f3f3f3f; const ll MINF = 0x3f3f3f3f3f3f3f3f; const double DINF = 0xffffffffffff; const int mod = 1e9+7; const int N = 2e6+5; struct node{ int typ; //类型 int x,y; int id; //记录输入相对位置 int val; int pos; //输出答案用 }a[N],tmp[N]; int n,w,tot; int ans[10005]; //答案数组 bool cmp(node a,node b){ if(a.x==b.x&&a.y==b.y) return a.id<b.id; if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int tree[N]; //tree数组按二进制存,根据n的末尾0的个数存取,树状数组 int lowbit(int x) { return x&(-x); } int Query(int x) //返回1到x的前缀和 { int res=0; while(x) { res+=tree[x]; x-=lowbit(x); } return res; } void Add(int x,int v) //实现a[x]+v; { while(x<=n) //注意这里是小于等于k,还是n,k是数据范围 { tree[x]+=v; x+=lowbit(x); } } void clearr(int x){ while(x<=n){ if(tree[x]==0) break; tree[x]=0; x+=lowbit(x); } } void cdq(int l,int r){ if(l>=r) return ; int mid=l+r>>1; cdq(l,mid); cdq(mid+1,r); int p=l,q=mid+1,k=l; while(p<=mid&&q<=r){ if(a[p].id<=a[q].id){ if(a[p].typ==1) Add(a[p].y,a[p].val); tmp[k++] = a[p++]; } else{ if(a[q].typ==2) ans[a[q].pos]+=Query(a[q].y)*a[q].val; tmp[k++] = a[q++]; } } while(p<=mid){ if(a[p].typ==1) Add(a[p].y,a[p].val); tmp[k++]=a[p++]; } while(q<=r){ if(a[q].typ==2) ans[a[q].pos]+=Query(a[q].y)*a[q].val; tmp[k++]=a[q++]; } for(int i=l;i<=r;i++){ clearr(a[i].y); a[i]=tmp[i]; } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); std::ios::sync_with_stdio(false); int s; scanf("%d%d",&s,&n); int opt,x,y,val,x1,x2,y1,y2; tot=0; int m=0; while(~scanf("%d",&opt)){ if(opt==3) break; if(opt==1){ scanf("%d%d%d",&x,&y,&val); a[++m]=node{1,x,y,m,val,0}; } else{ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); ++tot; //比x2,y2小的都加上,val赋值1 a[++m]=node{2,x2,y2,m,1,tot}; //因为他是中间矩阵,而我们加是1~x,1~y的加,所以多出来的要赋值成-1,来减掉,val赋值-1 a[++m]=node{2,x2,y1-1,m,-1,tot}; a[++m]=node{2,x1-1,y2,m,-1,tot}; //这里多减了一次,要加回来,val赋值1 a[++m]=node{2,x1-1,y1-1,m,1,tot}; ans[tot]+=(x2-x1+1)*(y2-y1+1)*s; //答案赋初值 } } sort(a+1,a+1+m,cmp); cdq(1,m); for(int i=1;i<=tot;i++) printf("%d ",ans[i]); return 0; }