[关闭]
@ysner 2018-04-05T12:20:34.000000Z 字数 3704 阅读 2499

CDQ分治总结

CDQ分治


基础知识

CDQ分治的优缺点:

( 1 )优点:代码量少,常数极小(@树套树),可以降低处理维数。(如果嵌套可以大段蒯
( 2 )缺点:必须离线处理

本质:

分治,只考虑 [L,mid]中元素对 [mid+1,R] 中元素的影响
(这意味着左边只修改,右边只统计答案,不会证正确性

写法:

据说写法很多,但我只会一种。。。
最后一维

step 1:分治
step 2:边处理边归并排序(左边插入,把能影响当前答案的插完后统计一个右边答案)
step 3:复原(清零)

前面几维

step 1:分治
step 2:排序(归并排序)
step 3:往下一维CDQ

关于使用

一层CDQ有时可以代替一层数据结构
如何CDQ套CDQ?
留坑,到时候yy一下结构和分治的时机

例题

T1

Luogu3368 【模板】树状数组 2
第一维排序,第二维CDQ
懒得打了,蒯下面那个板板就成

T2

Luogu3810 【模板】三维偏序(陌上花开)
第一维排序,第二维CDQ,第三维值域树状数组
(理论上可以打两层CDQ,但常数大)
贴个板板养眼,不记得背背就成

  1. il void CDQ(re int L,re int R)
  2. {
  3. if(L==R) return;
  4. re int mid=L+R>>1;
  5. CDQ(L,mid);CDQ(mid+1,R);
  6. re int l=L,r=mid+1,top=L-1;
  7. while(l<=mid&&r<=R)
  8. {
  9. if(q[l].b<=q[r].b) add(q[l].c,q[l].num),q1[++top]=q[l++];//三维偏序优先左边,因此一定要加等号
  10. else q[r].ans+=Query(q[r].c),q1[++top]=q[r++];
  11. }
  12. while(l<=mid) q1[++top]=q[l++];
  13. while(r<=R) q[r].ans+=Query(q[r].c),q1[++top]=q[r++];
  14. fp(i,L,mid) Clear(q[i].c);fp(i,L,R) q[i]=q1[i];
  15. }

Update:友情附赠树套树版本

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<cstring>
  7. #include<algorithm>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=5e5+100;
  15. struct node
  16. {
  17. int a,b,c,s,ans;
  18. bool operator < (const node &o) const {return a<o.a||(a==o.a&&b<o.b)||(a==o.a&&b==o.b&&c<o.c);}
  19. bool operator == (const node &o) const {return a==o.a&&b==o.b&&c==o.c;}
  20. }q[N],a[N];
  21. struct seg{int ls,rs,s,sum;}t[N*20];
  22. int n,k,top,ans[N],tot,rt[N];
  23. il int gi()
  24. {
  25. re int x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void Modify(re int &x,re int l,re int r,re int p,re int w)
  33. {
  34. if(!x) x=++tot;t[x].sum+=w;
  35. if(l==r) return;
  36. re int mid=l+r>>1;
  37. if(p<=mid) Modify(t[x].ls,l,mid,p,w);else Modify(t[x].rs,mid+1,r,p,w);
  38. }
  39. il int Query(re int x,re int l,re int r,re int ql,re int qr)
  40. {
  41. if(!x||(ql<=l&&r<=qr)) return t[x].sum;
  42. re int mid=l+r>>1,res=0;
  43. if(ql<=mid) res=Query(t[x].ls,l,mid,ql,qr);
  44. if(qr>mid) res+=Query(t[x].rs,mid+1,r,ql,qr);
  45. return res;
  46. }
  47. int main()
  48. {
  49. n=gi();k=gi();
  50. fp(i,1,n) q[i]=(node){gi(),gi(),gi(),1};
  51. sort(q+1,q+1+n);
  52. fp(i,1,n)
  53. if(q[i]==a[top]) a[top].s++;
  54. else a[++top]=q[i];
  55. fp(i,1,top)
  56. {
  57. for(re int j=a[i].b;j;j-=j&-j) a[i].ans+=Query(rt[j],1,k,1,a[i].c);
  58. ans[a[i].ans+a[i].s-1]+=a[i].s;
  59. for(re int j=a[i].b;j<=k;j+=j&-j) Modify(rt[j],1,k,a[i].c,a[i].s);
  60. }
  61. fp(i,0,n-1) printf("%d\n",ans[i]);
  62. return 0;
  63. }

T2

CJOJ2616 - 【HZOI 2016】偏序 I
要求四维偏序???
第一维排序,第二维CDQ,第三维CDQ,第四维值域树状数组
要实现CDQ的嵌套,只需在弄前几维CDQ时打个标记,标明它在这次CDQ中是在左边还是在右边处理的。往后到最后一维时,只有标记全为左才能修改,只有标记全为右才能统计进答案。
还有,前几维CDQ只用打标记和归并、分治就成了(所以几乎一模一样,可以直接蒯、再改一改q后的数字),什么修改、统计答案都是最后一维的事。
板子放下面

T3

CJOJ2375 - 【HZOI 2015】偏序 II
要求五维偏序???
第一维排序,第二到四维CDQ,第五维值域树状数组

  1. il void CDQ3(re int L,re int R)
  2. {
  3. if(L==R) return;
  4. re int mid=L+R>>1;
  5. CDQ3(L,mid);CDQ3(mid+1,R);
  6. re int top=L,l=L,r=mid+1;
  7. while(l<=mid&&r<=R)
  8. {
  9. if(q2[l].d<q2[r].d) //......
  10. {
  11. if(!q2[l].tag&&!q2[l].tag1) add(q2[l].e);
  12. q3[top++]=q2[l++];
  13. }
  14. else
  15. {
  16. if(q2[r].tag&&q2[r].tag1) ans+=Query(q2[r].e);
  17. q3[top++]=q2[r++];
  18. }
  19. }
  20. while(l<=mid) q3[top++]=q2[l++];//一一对应关系的结束,标志着左边再不能对右边造成影响
  21. while(r<=R)
  22. {
  23. if(q2[r].tag&&q2[r].tag1) ans+=Query(q2[r].e);//...
  24. q3[top++]=q2[r++];
  25. }
  26. fp(i,L,R)
  27. {
  28. if(!q2[i].tag&&!q2[i].tag1) Clear(q2[i].e);
  29. q2[i]=q3[i];
  30. }
  31. }
  32. il void CDQ2(re int L,re int R)
  33. {
  34. if(L==R) return;
  35. re int mid=L+R>>1;
  36. CDQ2(L,mid);CDQ2(mid+1,R);
  37. re int top=L,l=L,r=mid+1;
  38. while(l<=mid&&r<=R)
  39. {
  40. if(q1[l].c<q1[r].c) q1[l].tag1=0,q2[top++]=q1[l++];
  41. else q1[r].tag1=1,q2[top++]=q1[r++];
  42. }
  43. while(l<=mid) q1[l].tag1=0,q2[top++]=q1[l++];
  44. while(r<=R) q1[r].tag1=1,q2[top++]=q1[r++];
  45. fp(i,L,R) q1[i]=q2[i];
  46. CDQ3(L,R);
  47. }
  48. il void CDQ1(re int L,re int R)
  49. {
  50. if(L==R) return;
  51. re int mid=L+R>>1;
  52. CDQ1(L,mid);CDQ1(mid+1,R);
  53. re int top=L,l=L,r=mid+1;
  54. while(l<=mid&&r<=R)
  55. {
  56. if(q[l].b<q[r].b) q[l].tag=0,q1[top++]=q[l++];
  57. else q[r].tag=1,q1[top++]=q[r++];
  58. }
  59. while(l<=mid) q[l].tag=0,q1[top++]=q[l++];
  60. while(r<=R) q[r].tag=1,q1[top++]=q[r++];//归并排序???
  61. fp(i,L,R) q[i]=q1[i];
  62. CDQ2(L,R);
  63. }

然后因常数过大而被其它做法暴踩

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注