BZOJ 1176: [Balkan2007]Mokia（CDQ分治）
Posted On 2018年10月7日
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
Solution
三维CDQ分治（time,x,y）
时间已经默认有序
每一个询问操作显然只会被其左上的修改操作影响到
那么对于x进行归并排序，统计左区间对右区间的贡献时用树状数组维护即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<cstdio> using namespace std; typedef long long ll; inline int read() { register int f=1,k=0;register char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=160000+100; struct mc{int type,x,y;ll val;}rec[maxn<<2]; int b[maxn<<2],tmp[maxn<<2],w; int c[2000000+100]; inline void update(int x,const int&delta) { for(;x<=w+1;x+=x&-x)c[x]+=delta; } inline int query(int x) { register int ans=0; for(;x;x-=x&-x)ans+=c[x]; return ans; } void solve(const int l,const int r) { if (l==r)return; int mid=(l+r)>>1; solve(l,mid);solve(mid+1,r); register int p=l,q=mid+1; while (p<=mid&&q<=r) { if (rec[b[p]].x<rec[b[q]].x|| (rec[b[p]].x==rec[b[q]].x&&rec[b[p]].y<=rec[b[q]].y)) { if (!rec[b[p]].type)update(rec[b[p]].y,rec[b[p]].val); tmp[p+q-mid-1]=b[p];p++; } else { if (rec[b[q]].type)rec[b[q]].val+=query(rec[b[q]].y); tmp[p+q-mid-1]=b[q];q++; } } while (p<=mid) { if (!rec[b[p]].type)update(rec[b[p]].y,rec[b[p]].val); tmp[p+q-mid-1]=b[p];p++; } while(q<=r) { if (rec[b[q]].type)rec[b[q]].val+=query(rec[b[q]].y); tmp[p+q-mid-1]=b[q];q++; } for (register int i=l;i<=mid;i++)if (!rec[b[i]].type)update(rec[b[i]].y,-rec[b[i]].val); for (register int i=l;i<=r;i++)b[i]=tmp[i]; } int main() { int s=read();w=read();int tot=0; for(int opt=read(),x,y,xx,yy;opt!=3;opt=read()) if (opt==1)x=read(),y=read(),rec[++tot]=(mc){0,x,y,read()}; else x=read()-1,y=read()-1,xx=read(),yy=read(), rec[++tot]=(mc){1,x,y,1ll*x*y*s},rec[++tot]=(mc){2,xx,y,1ll*xx*y*s}, rec[++tot]=(mc){1,x,yy,1ll*x*yy*s},rec[++tot]=(mc){1,xx,yy,1ll*xx*yy*s}; for (register int i=1;i<=tot;i++)b[i]=i; solve(1,tot); for (register int i=1;i<=tot;i++) if (rec[i].type==2)printf("%lld\n",rec[i-1].val+rec[i+2].val-rec[i].val-rec[i+1].val); } |
Subscribe
0 评论