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
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
5
HINT
保证答案不会超过int范围
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
CDQ分治+树状数组~
和简单题一样啊……就是刚开始有个很巧妙的处理：在输入的时候把ans都加上(x2-x1)*(y2-y1)*m的值，就不用每个各自都加了~
注意更新b[]数组的时候是l1++，先记后加！
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int n,m,x,y,val,x1,y1,x2,y2,c[2000001],num,cnt,tot,ans[10001];struct node{int flag,x,y,v,poi,id;
}a[200001],b[200001];bool cmp(node u,node v)
{if(u.x!=v.x) return u.x<v.x;return u.poi<v.poi;
}int lowbit(int u)
{return u&(-u);
}void add(int u,int v)
{for(int i=u;i<=n;i+=lowbit(i)) c[i]+=v;
}int cal(int u)
{int totnum=0;for(int i=u;i;i-=lowbit(i)) totnum+=c[i];return totnum;
}void findd(int l,int r)
{if(l>=r) return;int mid=(l+r)>>1,l1=l,l2=mid+1;for(int i=l;i<=r;i++){if(a[i].flag==1 && a[i].poi<=mid) add(a[i].y,a[i].v);else if(a[i].flag==2 && a[i].poi>mid) ans[a[i].id]+=cal(a[i].y)*a[i].v;}for(int i=l;i<=r;i++) if(a[i].flag==1 && a[i].poi<=mid) add(a[i].y,-a[i].v);for(int i=l;i<=r;i++){if(a[i].poi<=mid) b[l1++]=a[i];else b[l2++]=a[i];}for(int i=l;i<=r;i++) a[i]=b[i];findd(l,mid);findd(mid+1,r);
}int main()
{scanf("%d%d",&m,&n);while(scanf("%d",&num)==1 && num!=3){if(num==1){scanf("%d%d%d",&x,&y,&val);a[++cnt]=(node){1,x,y,val,cnt,0};}else{scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1--;y1--;tot++;a[++cnt]=(node){2,x1,y1,1,cnt,tot};a[++cnt]=(node){2,x1,y2,-1,cnt,tot};a[++cnt]=(node){2,x2,y1,-1,cnt,tot};a[++cnt]=(node){2,x2,y2,1,cnt,tot};ans[tot]=(x2-x1)*(y2-y1)*m;}}sort(a+1,a+cnt+1,cmp);findd(1,cnt);for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);return 0;
}