Bzoj2683 简单题 [CDQ分治]

时间:2022-06-01 23:58:01

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+遍了,是不是也快要顿悟了呢……

________

 /*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n;
struct opt{
int flag;
int x,y,w;
int t;
int id;
}a[mxn*],b[mxn*];
int cnt=;
int cmp(opt q,opt e){
if(q.x==e.x){
if(q.y==e.y)return q.flag<e.flag;
return q.y<e.y;
}
return q.x<e.x;
}
int ans[mxn];
int t[mxn*];
void add(int x,int v){while(x<=n){t[x]+=v;x+=x&-x;}return;}
int sum(int x){
int res=;
while(x){res+=t[x];x-=x&-x;}
return res;
}
void solve(int l,int r){
if(l>=r)return;
int i,j,mid=(l+r)>>;
int l1=l,l2=mid+;
for(i=l;i<=r;i++){
if(a[i].flag== && a[i].t<=mid) add(a[i].y,a[i].w);
else if(a[i].flag== && a[i].t>mid) ans[a[i].id]+=sum(a[i].y)*a[i].w;
}
for(i=l;i<=r;i++)
if(a[i].flag== && a[i].t<=mid) add(a[i].y,-a[i].w);
for(i=l;i<=r;i++)
if(a[i].t<=mid)b[l1++]=a[i];
else b[l2++]=a[i];
for(i=l;i<=r;i++)a[i]=b[i];
solve(l,mid);solve(mid+,r);
return;
}
int main(){
n=read();
int i,j,x,y,c,v;
int id=;
while(){
c=read();
if(c==)break;
if(c==){//修改
x=read();y=read();v=read();
a[++cnt].flag=;a[cnt].x=x;a[cnt].y=y;a[cnt].w=v;
a[cnt].t=cnt;
}
else{//查询
x=read();y=read();c=read();v=read();
a[++cnt].flag=;a[cnt].x=x-;a[cnt].y=y-;
a[cnt].w=;a[cnt].t=cnt;a[cnt].id=++id;
a[++cnt].flag=;a[cnt].x=x-;a[cnt].y=v;
a[cnt].w=-;a[cnt].t=cnt;a[cnt].id=id;
a[++cnt].flag=;a[cnt].x=c;a[cnt].y=y-;
a[cnt].w=-;a[cnt].t=cnt;a[cnt].id=id;
a[++cnt].flag=;a[cnt].x=c;a[cnt].y=v;
a[cnt].w=;a[cnt].t=cnt;a[cnt].id=id;
}
}
sort(a+,a+cnt+,cmp);
solve(,cnt);
for(i=;i<=id;i++){
printf("%d\n",ans[i]);
}
return ;
}