首页 > 代码库 > Bzoj2683 简单题 [CDQ分治]

Bzoj2683 简单题 [CDQ分治]

2024-08-29 01:16:44   222人阅读

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 1071  Solved: 428

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

 

命令

参数限制

内容

1 x y A

1<=x,y<=N，A是正整数

将格子x,y里的数字加上A

2 x1 y1 x2 y2

1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和

3

无

终止程序

Input

输入文件第一行一个正整数N。
接下来每行一个操作。
 

Output

对于每个2操作，输出一个对应的答案。
 

Sample Input

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

1<=N<=500000,操作数不超过200000个，内存限制20M。

对于100%的数据，操作1中的A不超过2000。

Source

 

CDQ分治

第4遍回顾之前抄的代码的时候，突然顿悟。

个人理解，这种分治方法类似于做矩形面积并时候用到的扫描线法。将每个区间修改操作拆成插入/删除，和每个询问操作一起按横坐标x升序排序。

用一个一维数组记录“当前横坐标”对应的y轴情况，从左往右扫描所有操作，并用差分的方式完成修改（在时间维度上差分），记录答案。

↑该一维数组可以用树状数组优化，扫描操作可以用分治方法优化（每层分治时处理前半部分操作对后半部分查询的影响）。

　　↑组合起来就成了CDQ分治。

________

PS1:　这时我想起，两三个个月前RLQ说他研究出一种用树状数组乱搞二维大数据的做法，当时没怎么听懂，也没太在意……卧槽，原来是CDQ分治？

　　　 CDQ分治要是晚出现两年，就变成RLQ分治了……%%%%%

PS2:   之前抄的LCT也已经回顾了10+遍了，是不是也快要顿悟了呢……

________

 

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=200010; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13     return x*f;14 }15 int n;16 struct opt{17     int flag;18     int x,y,w;19     int t;20     int id;21 }a[mxn*10],b[mxn*10];22 int cnt=0;23 int cmp(opt q,opt e){24     if(q.x==e.x){25         if(q.y==e.y)return q.flag<e.flag;26         return q.y<e.y;27     }28     return q.x<e.x;29 }30 int ans[mxn];31 int t[mxn*5];32 void add(int x,int v){while(x<=n){t[x]+=v;x+=x&-x;}return;}33 int sum(int x){34     int res=0;35     while(x){res+=t[x];x-=x&-x;}36     return res;37 }38 void solve(int l,int r){39     if(l>=r)return;40     int i,j,mid=(l+r)>>1;41     int l1=l,l2=mid+1;42     for(i=l;i<=r;i++){43         if(a[i].flag==1 && a[i].t<=mid) add(a[i].y,a[i].w);44         else if(a[i].flag==2 && a[i].t>mid) ans[a[i].id]+=sum(a[i].y)*a[i].w;45     }46     for(i=l;i<=r;i++)47         if(a[i].flag==1 && a[i].t<=mid) add(a[i].y,-a[i].w);48     for(i=l;i<=r;i++)49         if(a[i].t<=mid)b[l1++]=a[i];50         else b[l2++]=a[i];51     for(i=l;i<=r;i++)a[i]=b[i];52     solve(l,mid);solve(mid+1,r);53     return;54 }55 int main(){56     n=read();57     int i,j,x,y,c,v;58     int id=0;59     while(1){60         c=read();61         if(c==3)break;62         if(c==1){//修改 63             x=read();y=read();v=read();64             a[++cnt].flag=1;a[cnt].x=x;a[cnt].y=y;a[cnt].w=v;65             a[cnt].t=cnt;66         }67         else{//查询 68             x=read();y=read();c=read();v=read();69             a[++cnt].flag=2;a[cnt].x=x-1;a[cnt].y=y-1;70                 a[cnt].w=1;a[cnt].t=cnt;a[cnt].id=++id;71             a[++cnt].flag=2;a[cnt].x=x-1;a[cnt].y=v;72                 a[cnt].w=-1;a[cnt].t=cnt;a[cnt].id=id;73             a[++cnt].flag=2;a[cnt].x=c;a[cnt].y=y-1;74                 a[cnt].w=-1;a[cnt].t=cnt;a[cnt].id=id;75             a[++cnt].flag=2;a[cnt].x=c;a[cnt].y=v;76                 a[cnt].w=1;a[cnt].t=cnt;a[cnt].id=id;77         }78     }79     sort(a+1,a+cnt+1,cmp);80     solve(1,cnt);81     for(i=1;i<=id;i++){82         printf("%d\n",ans[i]);83     }84     return 0;85 }

 

Bzoj2683 简单题 [CDQ分治]


联系
我们