CDQ分治总结(CDQ,树状数组,归并排序)

闲话CDQ是什么?是一个巨佬,和莫队、HJT(不是我这个蒟蒻)一样,都发明出了在OI中越来越流行的算法/数据结构。CDQ分治思想分治就是分治,“分而治之”的思想。那为什么会有CDQ分治这样的称呼呢?这一类分治有一个重要的思想——用一个子问题来计算对另一个子问题的贡献。有了这种思想,就可以方便地解决更复杂的问题。这样一句话怎样理解好呢?还是做做题目吧。例题1三维偏序问题洛谷题目传送门即给出若干元素,每个元素有三个属性值(a,b,c),询问对于每个元素(i),满足(a_jleq a_i,b_jleq b_i,c_jleq c_i)(j)的个数不用着急,先从简单的问题开始试想一下二位偏序也就是(a_jleq a_i,b_jleq b_i)怎么做先按(a)为第一关键字,(b)为第二关键字排序,那么我们就保证了第一维(a)的有序。于是,对于每一个(i),只可能(1)(i-1)的元素会对它有贡献,那么直接查(1)(i-1)的元素中满足(b_jleq b_i)的元素个数。具体实现?动态维护(b)的树状数组,从前到后扫一遍好啦,(O(nlog n))。那么三维偏序呢?我们只有在保证前两位都满足的情况下才能计算答案了。仍然按(a)为第一关键字,(b)为第二关键字,(c)为第三关键字排序,第一维保证左边小于等于右边了。为了保证第二维也是左边小于等于右边,我们还需要排序。想到归并排序是一个分治的过程,我们可不可以在归并的过程中,统计出在子问题中产生的对答案贡献呢?现在我们有一个序列,我们把它递归分成两个子问题,子问题进行完归并排序,已经保证(b)有序。此时,两个子问题间有一个分界线,原来第一维左边小于等于右边,所以现在分界线左边的任意一个的(a)当然还是都小于右边的任意一个。那不等于说,只有分界线左边的能对右边的产生贡献?于是,问题降到了二维。我们就可以排序了,归并排序(左边的指针为(j),右边的为(i))并维护(c)的树状数组,如果当前(b_jleq b_i),说明(j)可以对后面加入的满足(c_jleq c_i)(i)产生贡献了,把(c_j)加入树状数组;否则,因为后面加入的(j)都不会对(i)产生贡献了,所以就要统计之前被给的所有贡献了,查询树状数组(c_i)的前缀和。这是在分治中统计的子问题的答案,跟总答案有怎样的关系呢?容易发现,每个子问题统计的只有跨越分界线的贡献,反过来看,每一个能产生贡献的(i,j),有且仅有一个子问题,两者既同时被包含,又在分界线的异侧。那么所有子问题的贡献加起来就是总答案。算法的大致思路就是这样啦。至于复杂度,(T(n)=O(nlog k)+T(frac 2 n)=O(nlog nlog k))。当然还有不少细节问题。最大的问题就在于,可能有完全相同的元素。这样的话,本来它们相互之间都有贡献,可是cdq的过程中只有左边的能贡献右边的。这可怎么办呢?我们把序列去重,这样现在就没有相同的了。给现在的每个元素一个权值(v)等于出现的次数。中间的具体实现过程也稍有变化,在树状数组中插入的值是(v)而不是(1)了,最后统计答案时,也要算上相同元素内部的贡献,ans+=v-1。写法上,为了防止sort和归并排序中空间移动太频繁,没有对每个元素封struct,这样的话就要膜改一下cmp函数(蒟蒻也是第一次发现cmp可以这么写)蒟蒻还是觉得开区间好写一些吧。。。当然闭区间好理解些。。。#include<cstdio> #include<cstring> #include<algorithm> #define RG register #define R RG int using namespace std; const int N=1e5+9,SZ=2.2e6; char buf[SZ],*pp=buf-1;//fread必备 int k,a[N],b[N],c[N],p[N],q[N],v[N],cnt[N],ans[N],*e; inline int in(){ while(*++pp<'-'); R x=*pp&15; while(*++pp>'-')x=x*10+(*pp&15); return x; } void out(R x){ if(x>9)out(x/10); *++pp=x%10|'0'; } inline bool cmp(R x,R y){//直接对数组排序,注意三关键字 return a[x]<a[y]||(a[x]==a[y]&&(b[x]<b[y]||(b[x]==b[y]&&c[x]<c[y]))); } inline void upd(R i,R v){//树状数组修改 for(;i<=k;i+=i&-i)e[i]+=v; } inline int ask(R i){//树状数组查前缀和 R v=0; for(;i;i-=i&-i)v+=e[i]; return v; } void cdq(R*p,R n){//处理一个长度为n的子问题 if(n==1)return; R m=n>>1,i,j,k; cdq(p,m);cdq(p+m,n-m);//递归处理 memcpy(q,p,n<<2);//归并排序 for(k=i=0,j=m;i<m&&j<n;++k){ R x=q[i],y=q[j]; if(b[x]<=b[y])upd(c[p[k]=x],v[x]),++i;//左边小,插入 else cnt[y]+=ask(c[p[k]=y]) ,++j;//右边小,算贡献 } for(;j<n;++j)cnt[q[j]]+=ask(c[q[j]]);//注意此时可能没有完成统计 memcpy(p+k,q+i,(m-i)<<2); for(--i;~i;--i)upd(c[q[i]],-v[q[i]]);//必须这样还原树状数组,memset是O(n^2)的 } int main(){ fread(buf,1,SZ,stdin); R n=in(),i,j;k=in();e=new int[k+9]; for(i=0;i<n;++i) p[i]=i,a[i]=in(),b[i]=in(),c[i]=in(); sort(p,p+n,cmp); for(i=1,j=0;i<n;++i){ R x=p[i],y=p[j];++v[y];//模仿unique双指针去重,统计v if(a[x]^a[y]||b[x]^b[y]||c[x]^c[y])p[++j]=x; } ++v[p[j++]]; cdq(p,j); for(i=0;i<j;++i) ans[cnt[p[i]]+v[p[i]]-1]+=v[p[i]];//答案算好 for(pp=buf-1,i=0;i<n;++i) out(ans[i]),*++pp='n'; fwrite(buf,1,pp-buf+1,stdout); }例题二洛谷P4169 [Violet]天使玩偶/SJY摆棋子洛谷题目传送门不会KDT,然而CDQ当然是有优势的。第一眼就能发现每一个修改或查询都有三个属性,(x,y),还有时间戳。那么怎样把它转化为一般的三维偏序问题呢?假如所有记忆的点都在查询的点的左下角,那么就会只有(x,y)和时间戳三个维度都小于查询点的记忆点可以产生贡献,这就是三维偏序了。贡献是什么呢?设有若干(j)(i)产生了贡献,那么直接去绝对值,答案就是(min{x_i-x_j+y_i-y_j}),也就是(x_i+y_i-max{x_j+y_j}),这个还是可以用树状数组,只不过改成维护前缀最大值。第一维时间戳,输入已经排好序了;第二位(x)归并;第三位(y)树状数组统计答案。然而假设并不成立。但是我们可以发现,每个能产生贡献的点只可能会在查询点的四个方向(左下,左上,右下,右上),那么对所有点还要进行(3)遍坐标翻转(新坐标等于值域减去原坐标),做(4)遍CDQ,就可以统计到每个方向的最优答案,最后再取(min)即可。(n,m=300000),值域(1000000),一看这(O((n+m)log(n+m)log k))好大,还要跑(4)遍,真的不会T么?所以还是要优化一些细节。首先,蒟蒻仍然沿用三维偏序模板的做法,没有对元素封struct以减少空间交换,这样在做完坐标翻转后也能更快还原,直接for一遍初始化。然而也会带来数组的频繁调用,蒟蒻也在怀疑这种优化的可行性,还望Dalao指教。接着,我们发现左边有(n)个元素都确定了是记忆点。也就是说,我们不必对(n+m)个点都跑CDQ了,只对后面(m)个点跑,前面的(n)个点直接预处理按(x)第一关键字、(y)第二关键字sort,这样复杂度就降到了(O(nlog n+mlog mlog k+nlog k))了。然而做完坐标翻转后也别忘了处理一下。如果这一次翻转的是(y),那么(x)不会受到影响;如果翻转的是(x),那么也直接翻转数组就好啦!至于fread什么的用上也好。加上这一堆优化,代码就有90行了。然后一交上去就1A了!?平时习惯了满屏殷红的WA,蒟蒻也不得不感叹,比起不少数据结构,CDQ真是思路板又好写还好调。然而BZOJ的(n,m)都有(500000),CDQ过不了。。。。。。还是stO洛谷里楼上CDQ跑得超快的巨佬吧,蒟蒻不会卡常。#include<cstdio> #include<cstring> #include<algorithm> #define RG register #define I inline void #define R RG int #define gc if(++pp==pe)fread (pp=buf,1,SZ,stdin) #define pc(C) *pp=C;if(++pp==pe)fwrite(pp=buf,1,SZ,stdout) const int N=3e5,D=1e6+2,SZ=1<<19,INF=20020307; char buf[SZ],*pe=buf+SZ,*pp=pe-1; int x[N],y[N],p[N],q[N],f[N],ans[N],e[D+1]; bool t[N]; struct NODE{ int x,y; inline bool operator<(RG NODE b)const{ return x<b.x||(x==b.x&&y<b.y); } }a[N];//前n个点 inline int in(){ gc;while(*pp<'-')gc; R x=*pp&15;gc; while(*pp>'-'){x*=10;x+=*pp&15;gc;} return x; } I out(R x){ if(x>9)out(x/10); pc(x%10|'0'); } I min(R&x,R y){if(x>y)x=y;} I upd(R i,R v){for(;i<=D;i+=i&-i)if(e[i]<v)e[i]=v;} I qry(R i,R&v){for(;i ;i-=i&-i)if(v<e[i])v=e[i];} I clr(R i) {for(;i<=D;i+=i&-i)e[i]=0;} void cdq(R*p,R m){//三维偏序Dalao们都会吧 if(m==1)return; R n=m>>1,i,j,k; cdq(p,n);cdq(p+n,m-n); memcpy(q,p,m<<2); for(k=i=0,j=n;i<n&&j<m;++k) if(x[q[i]]<=x[q[j]]){ if(!t[q[i]])upd(y[q[i]],x[q[i]]+y[q[i]]); p[k]=q[i++]; } else{ if(t[q[j]])qry(y[q[j]],f[q[j]]); p[k]=q[j++]; } for(;j<m;++j) if(t[q[j]])qry(y[q[j]],f[q[j]]); memcpy(p+k,q+i,(n-i)<<2);//注意收尾和清空 for(--i;~i;--i)clr(y[q[i]]); } int main(){ R n=in(),m=in(),i,j,k; for(i=0;i<n;++i) a[i].x=in()+1,a[i].y=in()+1; std::sort(a,a+n);//n个点预排序 for(i=0;i<m;++i){ if((t[i]=in()-1))ans[i]=INF;//注意给极大值 x[i]=in()+1;y[i]=in()+1;//BIT不能有0下标,所以改一下 } for(k=1;k<=4;++k){ for(i=0;i<m;++i)p[i]=i;//很快就可以初始化序列 cdq(p,m); for(i=j=0;i<n&&j<m;){//外面统计还是和CDQ一样,只是不用归并了 if(a[i].x<=x[p[j]]) upd(a[i].y,a[i].x+a[i].y),++i; else{ if(t[p[j]])qry(y[p[j]],f[p[j]]); ++j; } } for(;j<m;++j) if(t[p[j]])qry(y[p[j]],f[p[j]]); memset(e,0,sizeof(e)); for(i=0;i<m;++i) if(t[i]&&f[i])min(ans[i],x[i]+y[i]-f[i]),f[i]=0; if(k==4)break; if(k&1){//第一次、第三次上下翻 for(i=0;i<n;++i)a[i].y=D-a[i].y; for(i=0;i<m;++i)y[i]=D-y[i]; } else{//第二次左右翻 for(i=0;i<n;++i)a[i].x=D-a[i].x; for(i=0;i<m;++i)x[i]=D-x[i]; for(i=0,j=n-1;i<j;++i,--j)std::swap(a[i],a[j]);//注意仍要保证x不降 } } for(pp=buf,i=0;i<m;++i) if(t[i]){out(ans[i]);pc('n');} fwrite(buf,1,pp-buf,stdout); return 0; }

相关内容推荐