「分治」-cdq分治

cdq分治是一种分治算法：

一种分治思想,必须离线,可以用来处理序列上的问题(比如偏序问
题),还可以优化1D/1D类型的DP。
• 算法的大体思路我们可以用点对来描述。假定我们有一个长度为n的序列,要处理序列中元素点对间的关系。定义一个操作cdq(l,r)表示当前处理序列上区间[L,R]的点对关系。那么我们需要找到[L,R]的中点M,将不同的点对分为三类:
• A:两个点都在区间[L,M]上
• B:两个点都在区间[M+1,R]上
• C:两个点分别在[L,M]和[M+1,R]上。
对于前两种情况,分别用cdq(L,M),cdq(M+1,R)解决,也就是甩锅给下一层。
对于第三种情况,我们需要想方设法在当前层的cdq(L,R)中解决。
在解决当前层的问题时,利用已经处理好的左右两边的信息,具体视不同题目而
定。

其实，这样的算法很帅！

例题：

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

这道题就是一道裸的cdq模板题，但是对于初学的菜鸡（就是我）来说还是异常的艰难，我们知道对于普通的二维偏序问题，我们的求解思路就是归并排序（有时也不一定），所以当求解三维偏序的时候我们还是要借鉴二维偏序的思路，求解的时候先进行三元组排序，然后在递归过程中将后两元排序，然后使用一个数据结构来维护第三维偏序，进行求解，其实可以把这道题当作求解三维偏序的板子，其实遇到三维偏序的题就可以想一想是不是cdq分治;

本道题的板子实现是依靠一堆排序实现的，我因为懒得打（没错，本人很懒）归并排序，所以就是用STL中的sort，从而时间上比别人多了一个log，但还是A了，就是慢的一匹

• 首先将所有元素三元组排序并去重,那么权值a已经随下标有序。假设我们当前处理区间[L,R]内的元素。设M为区间中点,我们分别在[L,M][M+1,R]两个区间中对第二维排序,那么[L,M]内所有元素的第一维一定小于[M+1,R]的元素,维护一个单调指针,按照第二维权值从小到大将[L,M]的元素加入树状数组,同时在树状数组中查询前缀和即可保障三个维度都是小于关系。具体实现中,我们可以在递归处理的同时完对第二维的归并排,而不用额外消耗时间使用快速排序

如果还是很蒙蔽，那就看代码！

 1 inline void cdq(int l,int r)
 2 {
 3     if(l==r) return;
 4     int m=l+r>>1,pl=l,pr=m+1,p=l;
 5     cdq(l,m),cdq(m+1,r);//递归处理两个子区间
 6     while(pl<=m&&pr<=r)
 7     {
 8         if(s[pl].b<=s[pr].b) q[p++]=s[pl++];
 9         else q[p]=s[pr++],mk[p++]=1;
10     }
11     while(pl<=m) q[p++]=s[pl++];
12     while(pr<=r) q[p]=s[pr++],mk[p++]=1;
13     for(int i=l;i<=r;++i) 
14     {
15         if(mk[i]) res[q[i].id]+=bit.sum(q[i].c);
16         else bit.add(q[i].c,q[i].w);
17     }
18     for(int i=l;i<=r;++i) 
19     {
20         if(!mk[i]) bit.add(q[i].c,-q[i].w);
21         else mk[i]=0;
22         s[i]=q[i];
23     }
24 }

就是这个，这就是cdq的核心部分，我在使用cdq的时候也认识到了分治算法的重要性，之前一直都吧递归的程序以及函数拒之门外，但是其实他们的效率也不差，而且好想是真的;（但是研发一个新的算法还是不容易的！）%%%cdq

然后就是我的多个log，跑的极慢的程序：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 using namespace std;
 8 struct re{int a,b,c,cnt,ans;}s[1000000],v[1000000];
 9 int cnt[1000000],q[1000000],tree[1000000],ans[1000000];
10 int tott,n,k;
11 inline int read()
12 {
13     int ss=0;char bb=getchar();
14     while(bb<48||bb>57)bb=getchar();
15     while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar();
16     return ss;
17 }
18 int lowbit(int x){return x&(-x);}
19 bool cmp(re a,re b){return a.b<b.b||(a.b==b.b&&a.c<b.c);}
20 bool cmp2(re a,re b){return a.a<b.a||(a.a==b.a&&cmp(a,b));}
21 void upd(int x,int vv){while(x<=k){tree[x]+=vv;x+=lowbit(x);}}
22 int query(int x){int sum=0;while(x){sum+=tree[x];x-=lowbit(x);}return sum;}
23 void cdq(int l,int r)
24 {
25     if(l==r)return ;
26     int mid=(l+r)>>1;
27     cdq(l,mid);
28     cdq(mid+1,r);
29     sort(v+l,v+mid+1,cmp);
30     sort(v+mid+1,v+r+1,cmp);
31     int l1=l,l2=mid+1;
32     while(l2<=r)
33     {
34         while(l1<=mid&&v[l1].b<=v[l2].b)upd(v[l1].c,v[l1].cnt),++l1;
35         v[l2].ans+=query(v[l2].c);++l2;
36     }
37     for(int i=l;i<l1;i++)upd(v[i].c,-v[i].cnt);
38 }
39 int main()
40 {
41     //freopen("ccf.txt","r",stdin);
42     n=read(),k=read();
43     for(int i=1;i<=n;i++)
44         s[i].a=read(),s[i].b=read(),s[i].c=read();
45     sort(s+1,s+1+n,cmp2);
46     for(int i=1,j=1;i<=n;i=j)
47     {
48         v[++tott]=s[i];
49         while(s[i].a==s[j].a&&s[i].b==s[j].b&&s[i].c==s[j].c&&j<=n)
50         j++,v[tott].cnt++;
51     }
52     cdq(1,tott);
53     for(int i=1;i<=tott;i++)cnt[v[i].ans+v[i].cnt-1]+=v[i].cnt;
54     for(int i=0;i<n;i++)printf("%d
",cnt[i]);
55     return 0;
56 }

cdq1

其实还是建议使用在递归的同时进行的排序，毕竟有的时候有些题并不那么友好。sort在平时水题的时候还是很好使的。但是效率实在是不高：

对比鲜明！

cdq在其他的地方（也就是题不那么板子的时候）也有出现！

例题2：

出

题目类型：传统评测方式：文本比较

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

第一行两个整数,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:表示输入结束

这道题首先一看，就先是想到之前IOI的那倒移动电话那道题。然后二维线段树开吗。等等，空间根本开不下啊，而且时间也会爆炸那怎么啊？玄学树套树....？不存在的，我也不会码啊！这是cdq就出场了，cdq是维护三维偏序问题，所以这道题当然可以抽象成三维偏序问题，只是稍变一下，按照题目的意思，这个矩形是可以有四个矩形进行容斥得到，所以我们一就是求对于x，y，满足三维偏序的点对的个数问题，cdq就直接搞定了！至此,这道题已经和前一题的三维偏序基本相同,不同点在于修改操作。那么我们改变策略,在分出两个子区间后,只考虑左区间的修改,对于左右端点都在右区间的查询操作产生的影响。按照这种分法,一定能保证所有查询操作能考虑到先前的修改操作。

所以这还是一道cdq的半裸题;

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cctype>
 4 #include<cstring>
 5 #include<vector>
 6 #include<algorithm>
 7 using namespace std;
 8 const int maxn=8000000;
 9 struct num{
10     int x,y,add,t,pos;
11 }G[maxn],ss[maxn];
12 int s,w,cnt=0,t=0,ans[maxn],tree[maxn];
13 #define debug(x) cout<<x<<" debug!"<<endl;
14 bool cmp(num a,num b)
15 {
16     if(a.x==b.x&&a.y==b.y)return a.pos<b.pos;
17     if(a.x==b.x)return a.y<b.y;
18     return a.x<b.x;
19 }
20 inline int lowbit(int t){return t&(-t);}
21 void add(int x,int y){while(x<=w){tree[x]+=y;x+=lowbit(x);}}
22 int query(int x){int res=0;while(x){res+=tree[x];x-=lowbit(x);}return res;}
23 void addq(int x1,int y1,int x2,int y2)
24 {
25     int pos=++cnt;
26     G[++t].pos=pos;G[t].t=t;G[t].x=x2;G[t].y=y2;G[t].add=1;
27     G[++t].pos=pos;G[t].t=t;G[t].x=x1-1;G[t].y=y1-1;G[t].add=1;
28     G[++t].pos=pos;G[t].t=t;G[t].x=x2;G[t].y=y1-1;G[t].add=-1;
29     G[++t].pos=pos;G[t].t=t;G[t].x=x1-1;G[t].y=y2;G[t].add=-1;
30 }
31 void cdq(int l,int r)
32 {
33     if(l>=r)return;
34     int mid=(l+r)>>1;
35     for(int i=l;i<=r;i++)
36     {
37         if(G[i].t<=mid&&!G[i].pos)add(G[i].y,G[i].add);
38         if(G[i].t>mid&&G[i].pos)ans[G[i].pos]+=G[i].add*query(G[i].y);
39     }
40     for(int i=l;i<=r;i++)
41     {
42         if(G[i].t<=mid&&!G[i].pos)add(G[i].y,-G[i].add);
43     }
44     int l1=l,l2=mid+1;
45     for(int i=l;i<=r;i++)
46     {
47         if(G[i].t<=mid)ss[l1++]=G[i];
48         else ss[l2++]=G[i];
49     }
50     for(int i=l;i<=r;i++)G[i]=ss[i];
51     cdq(l,mid);
52     cdq(mid+1,r);
53     return;
54 }
55 int main()
56 {
57     scanf("%d%d",&s,&w);
58     while(1)
59     {
60         int k;
61         scanf("%d",&k);
62         if(k==3)break;
63         if(k==1)
64         {
65             int xx,yy,zz;
66             scanf("%d%d%d",&xx,&yy,&zz);
67             //debug(xx);debug(yy),debug(zz);
68             G[++t].x=xx;
69             G[t].y=yy;
70             G[t].add=zz;
71             G[t].t=t;
72         }
73         else
74         {
75             int x1,x2,y1,y2;
76             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
77             addq(x1,y1,x2,y2);
78         }
79     }
80     sort(G+1,G+t+1,cmp);
81     cdq(1,t);
82     for(int i=1;i<=cnt;i++)printf("%d
",ans[i]);
83     return 0;
84 }

View Code

这道题也告诉我们其实很多题都是换汤不换药，只是吧题目背景换一下，别的套路还是一样的，但是不一定所有的都一样;

例题3：

入输出

题目类型：传统评测方式：Special Judge

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

第一行包含一个正整数

，表示敌军导弹数量；

下面行按顺序给出了敌军所有导弹信息：

第i+1行包含2个正整数

和

，分别表示第枚导弹的高度和速度。

输出包含两行。

第一行为一个正整数，表示最多能拦截掉的导弹数量；

第二行包含n个0到1之间的实数，第i个数字表示第i枚导弹被拦截掉的概率（你可以保留任意多位有效数字）。

相信这会使我们想到之前做的线性dp，但是那是这道题的简化办，就只有第一问，但是这有第二问，我们也发现之前只有一个两个限制条件，就是时间和高度，但是这道题有三个限制条件，分别是时间，高度和速度，这三个只有都满足的时候才能够对答案作出贡献，所以cdq分治，因为是三维偏序。然后就是要把dp的状态转移放到cdq的里面去，因为是让球概率，那么这也是一道假的概率题，只要使用合法的方案数比上总的方案数就可以得到答案;然后就要正着和倒着都各跑一遍，（这也是为了球总的方案数，也很好像），然后在递归过程中进行状态转移就行了！

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<vector>
  7 using namespace std;
  8 const int maxn=100000;
  9 inline int read()
 10 {
 11     int x=0,f=1;char cc;cc=getchar();
 12     while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();}
 13     while(cc>='0'&&cc<='9'){x=(x<<3)+(x<<1)+(cc^48);cc=getchar();}
 14     return x;
 15 }
 16 struct tree
 17 {
 18     int f;double w;
 19     tree(){f=0,w=0;}
 20 }t[maxn];
 21 int n;
 22 int st[maxn],top=0,th,tv;
 23 inline int lowbit(int x){return x&(-x);}
 24 inline void add(int p,int f,double w)
 25 {
 26     while(p<n)
 27     {
 28         if(t[p].f<f)
 29         {
 30             if(t[p].f==0)st[++top]=p;
 31             t[p].f=f;t[p].w=w;
 32         }
 33         else if(t[p].f==f)t[p].w+=w;
 34         p+=lowbit(p);
 35     }
 36     return;
 37 }
 38 tree ask(int p)
 39 {
 40     tree res;
 41     while(p)
 42     {
 43         if(t[p].f>res.f) res=t[p];
 44         else if(t[p].f==res.f) res.w+=t[p].w;
 45         p-=lowbit(p);
 46     }
 47     return res;
 48 }
 49 struct Dan
 50 {
 51     int h,v,f[2],id,t;
 52     double g[2];
 53 }a[maxn],q[maxn];
 54 int wh[maxn],wv[maxn],id[maxn];
 55 int rk[maxn];
 56 inline bool cmp(int x,int y){return a[x].h<a[y].h||(a[x].h==a[y].h&&a[x].id<a[y].id);}
 57 int cmpid(Dan a,Dan b){return a.id<b.id;}
 58 int cnt=0;
 59 void cdq(int l,int r,int mode)
 60 {
 61     if(l==r)
 62     {
 63         if(a[l].f[mode]<1){a[l].f[mode]=1;a[l].g[mode]=1;}
 64         return;
 65     }
 66     int mid=(l+r)>>1;
 67     memcpy(q+l,a+l,sizeof(Dan)*(r-l+1));
 68     int q1=l,q2=mid+1;
 69     for(int i=l;i<=r;i++)
 70         if(q[i].t<=mid)a[q1++]=q[i];     
 71         else a[q2++]=q[i];
 72     cdq(l,mid,mode);
 73     q1=l;
 74     for(int i=mid+1;i<=r;i++)
 75     {
 76         while(q1<=mid && a[q1].id<a[i].id) 
 77             add(a[q1].v,a[q1].f[mode],a[q1].g[mode]),q1++;
 78         tree res=ask(a[i].v);
 79         if(!res.f)continue;
 80         if(res.f+1>a[i].f[mode])
 81         {
 82             a[i].f[mode]=res.f+1;
 83             a[i].g[mode]=res.w;
 84         }
 85         else if(res.f+1==a[i].f[mode]) a[i].g[mode]+=res.w;
 86     }
 87     while(top){t[st[top]].w=0;t[st[top--]].f=0;}
 88     cdq(mid+1,r,mode);
 89     merge(a+l,a+mid+1,a+mid+1,a+r+1,q+l,cmpid);
 90     memcpy(a+l,q+l,sizeof(Dan)*(r-l+1));
 91     return;
 92 }
 93 int main()
 94 {
 95     //freopen("cnm.txt","r",stdin);
 96     n=read();
 97     for(int i=1;i<=n;i++)
 98     {
 99         a[i].h=read();a[i].v=read();a[i].id=i;
100         wh[i]=a[i].h;wv[i]=a[i].v;
101         rk[i]=i;
102     }
103     sort(wh+1,wh+n+1);
104     sort(wv+1,wv+n+1);
105     th=unique(wh+1,wh+n+1)-wh-1;
106     tv=unique(wv+1,wv+n+1)-wv-1;
107     for(int i=1;i<=n;i++)
108     {
109         a[i].h=th-(lower_bound(wh+1,wh+th+1,a[i].h)-wh)+1;
110         a[i].v=tv-(lower_bound(wv+1,wv+tv+1,a[i].v)-wv)+1;
111     }
112     sort(rk+1,rk+n+1,cmp);
113     for(int i=1;i<=n;i++)a[rk[i]].t=i;
114     cdq(1,n,0);
115     for(int i=1;i<=n;i++)
116     {
117         a[i].h=th-a[i].h+1;
118         a[i].v=tv-a[i].v+1;
119         a[i].id=n-a[i].id+1;
120         a[i].t=n-a[i].t+1;
121     }
122     reverse(a+1,a+n+1);
123     cdq(1,n,1);
124     reverse(a+1,a+n+1);
125     double smm=0;
126     int ans=0;
127     for(register int i=1;i<=n;i++)
128         ans=max(ans,a[i].f[0]+a[i].f[1]-1);
129     printf("%d
",ans);
130     for(int i=1;i<=n;i++)
131         if(a[i].f[0]==ans)
132             smm+=a[i].g[0]*a[i].g[1]*1ll;
133     for(int i=1;i<=n;i++)
134     {
135         double res=a[i].g[0]*a[i].g[1];
136         if(a[i].f[0]+a[i].f[1]-1!=ans)printf("%.5lf ",0.0);
137         else printf("%.5f ",res/smm);
138     }
139     return 0;
140 }

lan

总结cdq的用处很大最起码不用使用复杂的树套树来维护一些东西，但是目前我知道的cdq好像都只能球三维偏序问题。

/////////////cdq专题我还没刷完，这个专题的坑还很大///////

「分治」-cdq分治

A. 陌上花开

题目描述

B. Mokia

题目描述

输入格式

C. 拦截导弹

题目描述

输入格式

输出格式