「BZOJ2683」简单题 - CDQ分治

92 阅读 0 评论 61 点赞

我是靠谱客的博主难过纸飞机，这篇文章主要介绍「BZOJ2683」简单题 - CDQ分治，现在分享给大家，希望可以做个参考。

题目描述

你有一个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	无	终止程序

输入格式

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

输出格式

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

数据范围

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

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

分析

若N比较小，则可以用二维的树状数组或线段树来做，但是500000，空间开不下，于是考虑离线CDQ。

所谓CDQ分治，是由金牌选手陈丹琪提出来的。普通的分治，只是递归左边，递归右边，返回。而CDQ分治分别递归左右两边，再计算由左边对右边的操作产生的影响。其实归并排序求逆序对就是简单的CDQ分治，先递归左边，再递归右边，再用两个指针分别从L，mid+1开始扫描，并计算左边与右边共同所产生的逆序对数。

对于本题，先将所有的操作离线读入，并将一个查询用前缀和的思想分为四个查询，修改就直接读入。递归边界是l==r，此时不需要处理，只有一个操作。递归处理左右两边，此时(L,mid)的时间一定再(mid+1,R)的前面，于是规定一个优先级，x为第一关键字，从小到大排，类型为第二关键字，修改优于查询。以后说操作的小于都按照此规定来。用两个指针p=L,q=mid+1，类似归并排序求逆序对一样。对于p,q，若p所指向的操作小于q所指向的操作，则说明p要优先，若p为修改，则再树状数组对应位置修改，p++，否则不管，因为左边的询问再递归左边的时候已经处理好了；否则，说明q要优先，若q为查询，则再树状数组对应位置查询，并记录答案。之后在将树状数组复位，以保证时间复杂度。对于当前所有的操作，用一个temp数组临时存下来，最后要赋值给原数组，保证x的有序。

这里的树状数组又是怎么回事？实际上，通过前缀和，已经将问题转化为x<=x0，y<=y0的所有格子上的数的和。因为x已经有序，即在当前操作之前的所有操作都是对与x<=x0，若此时y也有序，则直接统计即可。但可惜的是y并不有序，所以用树状数组统计y<=y0的所有数的和。最后一定要用循环复位，即将加上的减去，不能直接memset，要保证时间复杂度仅仅与L，R有关。

以上就是CDQ分治在本题的大致流程。不得不佩服陈丹琪，能想出这种分治算法。

接下来就是令人兴奋的代码环节。

代码

复制代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=500005;
const int M=300005*4;
struct Query {
LL x,y,type,w;//x,y为坐标,type为类型:0为修改,1为查询
LL val,id;//val为修改时加的值,id为查询后原答案的位置 
//w为查询时是该点的答案对总答案的贡献,加/减 
bool operator<(const Query&a) const {
if (x!=a.x) return x<a.x;//x为第一关键字 
return type<a.type;//type为第二关键字 
}
}a[M],temp[M];
LL n,op,pt,num;
LL ans[M],nm[M];
struct Bit {//结构体的树状数组更清晰 
LL c[N];
#define lowbit(x) ((x)&-(x))
void Add(int x,LL v) {
while (x<=n+1) {
c[x]+=v;
x+=lowbit(x);
}
}
int Ask(int x) {
int ret=0;
while (x) {
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
}bit;
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,t=l;
while (p<=mid&&q<=r) {//与归并求逆序对类似 
if (a[p]<a[q]) {
if (a[p].type==1) {
bit.Add(a[p].y,a[p].val);
}
temp[t++]=a[p++];
} else {
if (a[q].type==2) ans[a[q].id]+=a[q].w*bit.Ask(a[q].y);
temp[t++]=a[q++];
}
}
while (q<=r) {//对于剩余的操作 
if (a[q].type==2) ans[a[q].id]+=a[q].w*bit.Ask(a[q].y);
temp[t++]=a[q++];
}
for (int i=l;i<p;i++)//树状数组复位 
if (a[i].type==1) bit.Add(a[i].y,-(a[i].val));
while (p<=mid) temp[t++]=a[p++];
for (int i=l;i<=r;i++)
a[i]=temp[i];
}
int main() {
scanf("%lld",&n);
while (scanf("%lld",&op),op!=3) {
LL x,y,xx,yy,v;
if (op==1) {
scanf("%lld%lld%lld",&x,&y,&v);
x++;y++;//防止树状数组下标为0 
a[++pt]=(Query){x,y,1,0,v};//插入查询 
} else {
scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
++num;
x++;y++;xx++;yy++;
a[++pt]=(Query){x-1,y-1,2,1,0,num};//拆分询问 
a[++pt]=(Query){xx,yy,2,1,0,num};
a[++pt]=(Query){x-1,yy,2,-1,0,num};
a[++pt]=(Query){xx,y-1,2,-1,0,num};
}
}
CDQ(1,pt);
for (int i=1;i<=num;i++) printf("%lldn",ans[i]);
return 0;
}

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=500005;
const int M=300005*4;
struct Query {
LL x,y,type,w;//x,y为坐标,type为类型:0为修改,1为查询
LL val,id;//val为修改时加的值,id为查询后原答案的位置 
//w为查询时是该点的答案对总答案的贡献,加/减 
bool operator<(const Query&a) const {
if (x!=a.x) return x<a.x;//x为第一关键字 
return type<a.type;//type为第二关键字 
}
}a[M],temp[M];
LL n,op,pt,num;
LL ans[M],nm[M];
struct Bit {//结构体的树状数组更清晰 
LL c[N];
#define lowbit(x) ((x)&-(x))
void Add(int x,LL v) {
while (x<=n+1) {
c[x]+=v;
x+=lowbit(x);
}
}
int Ask(int x) {
int ret=0;
while (x) {
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
}bit;
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,t=l;
while (p<=mid&&q<=r) {//与归并求逆序对类似 
if (a[p]<a[q]) {
if (a[p].type==1) {
bit.Add(a[p].y,a[p].val);
}
temp[t++]=a[p++];
} else {
if (a[q].type==2) ans[a[q].id]+=a[q].w*bit.Ask(a[q].y);
temp[t++]=a[q++];
}
}
while (q<=r) {//对于剩余的操作 
if (a[q].type==2) ans[a[q].id]+=a[q].w*bit.Ask(a[q].y);
temp[t++]=a[q++];
}
for (int i=l;i<p;i++)//树状数组复位 
if (a[i].type==1) bit.Add(a[i].y,-(a[i].val));
while (p<=mid) temp[t++]=a[p++];
for (int i=l;i<=r;i++)
a[i]=temp[i];
}
int main() {
scanf("%lld",&n);
while (scanf("%lld",&op),op!=3) {
LL x,y,xx,yy,v;
if (op==1) {
scanf("%lld%lld%lld",&x,&y,&v);
x++;y++;//防止树状数组下标为0 
a[++pt]=(Query){x,y,1,0,v};//插入查询 
} else {
scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
++num;
x++;y++;xx++;yy++;
a[++pt]=(Query){x-1,y-1,2,1,0,num};//拆分询问 
a[++pt]=(Query){xx,yy,2,1,0,num};
a[++pt]=(Query){x-1,yy,2,-1,0,num};
a[++pt]=(Query){xx,y-1,2,-1,0,num};
}
}
CDQ(1,pt);
for (int i=1;i<=num;i++) printf("%lldn",ans[i]);
return 0;
}