[关闭]
@happyforever 2018-08-06T13:53:05.000000Z 字数 9093 阅读 653

CDQ分治

分治 CDQ分治

基本思想

1.要解决一系列包含修改和查询操作的问题，可以将这些问题排成一个序列，用一个区间[l,r]来表示
2.递归处理左区间[l,mid]和边区间[mid+1,r]
3.合并两个子问题的时候同时考虑到左区间[l,mid]内部的修改对右区间[mid+1,r]内产生的影响。即用左边的子问题帮助解决右边的子问题

与普通分治的主要区别：普通分治在合并两个子问题的时候[l,mid]不会对[mid+1,r]内的问题产生影响

一般步骤：
1.将整个操作序列分为两个长度相等的部分（分）
2.递归处理前一部分的子问题（治1）
3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）
4.递归处理后一部分子问题（治3）

用途

顶替高级数据结构

二维偏序问题

给定个有序数对，求对于每个，满足并且的有序对有多少个

回忆归并排序求逆序对的过程，在合并两个子区间的时候，要考虑到左边区间对右边区间的影响。即：每次从右边区间的有序序列中取出一个元素的时候，要把“以这个元素结尾的逆序对的个数”加上“左边区间有多少个元素比他大”。这是一个典型的CDQ分治的过程。

现在把这个问题拓展到二维偏序问题。在归并排序求逆序对的过程中，每个元素可以用一个有序对表示，其中a表示数组中的位置，b表示该位置对应的值。那么求的就是“对于每个有序对，有多少个有序对满足且”，这就是一个二维偏序问题。

注意到在求逆序对的问题中，a元素是默认有序的，即我们拿到元素的时候，数组中的元素是默认从第一个到最后一个按顺序排列的，所以才能在合并子问题的时候忽略a元素带来的影响。因为我们在合并两个子问题的过程中，左边区间的元素一定出现在右边区间的元素之前，即左边区间的元素的a都小于右边区间元素的a

那么对于二维偏序问题，在拿到所有有序对的时候，先把a元素从小到大排序。这时问题就变成了“求顺序对”，因为a元素已经有序，可以忽略a元素带来的影响，和“求逆序对”的问题是一样的。

那么考虑二维偏序问题的另一种解法：用树状数组代替CDQ分治，即常用的用树状数组求顺序对。在按照a元素排序之后，对于整个序列从左到右扫描，每次扫描到一个有序对，求出“扫描过的有序对中，有多少个有序对的b值小于当前b值”，可以用权值树状数组或者权值线段树实现。

然而当b的值非常大的时候，空间和时间上就会吃不消，便可以用CDQ分治代替
所以CDQ分治具有“顶替复杂的高级数据结构”的作用。

EX_二维偏序问题

给定一个N个元素的序列A（标号从1开始），初始值全部为0，对这个序列进行以下两种操作
1.格式为1 x k，表示将位置x的元素加上k
2.格式为2 x y，表示求出区间[x,y]所有元素的和

这是个经典的树状数组问题，现在考虑用CDQ分治解决
将其转化成二维偏序问题，每个操作用一个有序数对来表示，其中表示这是第几次操作，表示操作的位置，显然a是默认有序的，所以在合并子问题的过程中，就按照b从小到大的顺序进行合并

定义结构体Query包含3个元素：type，idx，val，其中idx表示操作的位置，type为1表示修改，val表示“加上的值”。
对于查询，用前缀和的思想把他分解成两个操作：sum[1,y]-sum[1,x-1]，即分解成两次前缀和的查询。在合并的过程中，type为2表示遇到了一个查询的左端点x-1，需要把该查询的结果减去当前“加上的值的前缀和”，type为3表示遇到了一个查询的右端点y，需要把查询的结果加上当前“加上的值的前缀和”，val表示“是第几个查询”。这样，我们就把每个操作转换成了带有附加信息的有序对(时间，位置)，然后对整个序列进行CDQ分治

需要注意的细节：
1.对于位置相同的操作，先修改后查询
2.合并问题的时候统计“加上的值的前缀和”，只能统计左边区间内的修改操作，改动查询结果的时候，只能修改右边区间内的查询结果。因为只有左边区间内的修改值对右边区间内的查询结果的影响还没有统计

例题

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  5. inline void read(int &n)
  6. {
  7.     n=0;int w=1;register char c=getchar();
  8.     while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
  9.     while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
  10.     n*=w;
  11. }
  13. typedef long long ll;
  14. const int N=500001;
  15. int n,m;
  16. struct Query{
  17.     int type,idx,val;
  18.     bool operator<(const Query &x)const
  19.     {return idx==x.idx ? type<x.type : idx<x.idx;}
  20. }que[N*3],emp[N*3];
  21. int qidx,aidx,ans[N*3];
  23. void CDQ(int l,int r)
  24. {
  25.     if(r-l<=1)return ;
  26.     int mid=l+r>>1;
  27.     CDQ(l,mid),CDQ(mid,r);
  28.     ll sum=0;
  29.     int i=l,j=mid,k=0;
  30.     while(i<mid&&j<r)
  31.     {
  32.         if(que[i]<que[j])//只统计左边区间的修改值
  33.         {
  34.             if(que[i].type==1)
  35.                 sum+=que[i].val;
  36.             emp[k++]=que[i++];
  37.         }
  38.         else//只修改右边区间内的查询结果 
  39.         {
  40.             if(que[j].type==2)
  41.                 ans[que[j].val]-=sum;
  42.             else
  43.                 if(que[j].type==3)
  44.                     ans[que[j].val]+=sum;
  45.             emp[k++]=que[j++];
  46.         }
  47.     }
  48.     while(i<mid)emp[k++]=que[i++];
  49.     while(j<r)
  50.     {
  51.         if(que[j].type==2)
  52.             ans[que[j].val]-=sum;
  53.         else
  54.             if(que[j].type==3)
  55.                 ans[que[j].val]+=sum;
  56.         emp[k++]=que[j++];
  57.     }
  58.     for(int x=0;x<k;++x)
  59.         que[x+l]=emp[x];
  60. }
  62. int main()
  63. {
  64.     read(n),read(m);
  65.     for(int i=1;i<=n;++i)
  66.     {
  67.         que[qidx].idx=i;que[qidx].type=1;
  68.         read(que[qidx].val);++qidx;
  69.     }
  70.     for(int l,r,i=0;i<m;++i)
  71.     {
  72.         read(que[qidx].type);
  73.         if(que[qidx].type==1)
  74.             read(que[qidx].idx),read(que[qidx].val);
  75.         else
  76.         {//把查询操作分为两部分 
  77.             read(l),read(r);
  78.             que[qidx].idx=l-1;que[qidx].val=aidx;++qidx;
  79.             que[qidx].type=3;que[qidx].idx=r;que[qidx].val=aidx;
  80.             ++aidx;
  81.         }
  82.         ++qidx;
  83.     }
  84.     CDQ(0,qidx);
  85.     for(int i=0;i<aidx;++i)
  86.         printf("%lld\n",ans[i]);
  87.     return 0;
  88. }

三维偏序问题

给定N个有序三元组(a,b,c)，求对于每个三元组，有多少个三元组满足且且

首先给出不用CDQ分治的方法：树套树
先按照a元素排序，从左到右扫描。按照b元素构造权值树状数组，树状数组每个节点按照c元素构造平衡树。不仅常数大，而且码量大，还容易写错

CDQ分治做法：
类似二维偏序问题，先按照a元素从小到大排序，忽略a元素的影响。然后CDQ分治，按照b元素从小到大的顺序进行归并操作。但是这时候没办法像求逆序对一样简单地统计个数了。那么对于c元素的处理，比较好的方案就是借助权值树状数组。每次从右边的序列中取出三元组(a,b,c)时，对树状数组查询c值小于(a,b,c)的三元组有多少个；每次从左边序列取出三元组(a,b,c)的时候，根据c值在树状数组中进行修改。注意，每次使用完树状数组记得把树状数组归零！

例题

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring> 
  4. #include <cstdio>
  6. typedef long long ll;
  7. const int N=2e5+5;
  8. inline void read(int &n)
  9. {
  10.     char c=getchar();n=0;int w=1;
  11.     while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
  12.     while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
  13.     n*=w;
  14. }
  16. int n,maxVal;
  17. struct Operation{
  18.     int a,b,c,w;
  19.     int f;//ans
  20.     bool operator <(const Operation &r)const
  21.     {return (a==r.a&&b==r.b)?c<r.c:(a==r.a?b<r.b:a<r.a);}
  22. }a[N],t[N];
  23. int c[N];
  24. inline int lowbit(int x){return x&-x;}
  26. inline void add(int p,int v)
  27. {
  28.     for(;p<=maxVal;p+=lowbit(p))
  29.         c[p]+=v;
  30. }
  32. inline int sum(int p)
  33. {
  34.     int emp=0;
  35.     for(;p;p-=lowbit(p))
  36.         emp+=c[p];
  37.     return emp;
  38. }
  39. int ans[N];
  40. void CDQ(int l,int r)
  41. {
  42.     if(l==r)return;
  43.     int mid=(l+r)>>1;
  44.     CDQ(l,mid);CDQ(mid+1,r);
  45.     int i=l,j=mid+1,p=l;
  46.     while(i<=mid||j<=r)
  47.     {
  48.         if(j>r||(i<=mid&&a[i].b<=a[j].b))
  49.             add(a[i].c,a[i].w),t[p++]=a[i++];
  50.         else
  51.         {
  52.             a[j].f+=sum(a[j].c);
  53.             t[p++]=a[j++];
  54.         }
  55.     }
  56.     for(int i=l;i<=mid;++i)
  57.         add(a[i].c,-a[i].w);
  58.     for(int i=l;i<=r;++i)
  59.         a[i]=t[i];
  60. }
  61. int main()
  62. {
  63.     read(n);read(maxVal);
  64.     for(int i=1;i<=n;++i)
  65.     {
  66.         read(a[i].a);
  67.         read(a[i].b);
  68.         read(a[i].c);
  69.         a[i].w=1;
  70.     }
  71.     std::sort(a+1,a+1+n);
  73.     int p=1;
  74.     for(int i=2;i<=n;++i)
  75.     {
  76.         if(a[i].a==a[p].a&&a[i].b==a[p].b&&a[i].c==a[p].c)
  77.             ++a[p].w;
  78.         else    a[++p]=a[i];
  79.     }
  81.     int n_=n;
  82.     n=p;
  83.     CDQ(1,n);
  84.     for(int i=1;i<=n;++i)
  85.         ans[a[i].f+a[i].w-1]+=a[i].w;
  86.     for(int i=0;i<n_;++i)
  87.         printf("%d\n",ans[i]);
  88.     return 0;
  89. }

EX_三维偏序问题

平面上有N个点，每个点的横纵坐标在之间，有个询问，每个询问为查询在指定矩形之内有多少个点，矩形用的方式给出，其中为左下角坐标，为右上角坐标

把每个点的位置变成一个修改操作，用三元组(时间，横坐标，纵坐标)来表示，把每个查询分解成4个前缀和查询，同样用三元组来表示。对于修改操作，每个三元组没有附加信息；对于查询操作，每个三元组的附加信息为“第几个查询”和“对结果的影响是+还是-，用+1表示+，用-1表示-”。操作到来的时间是默认有序的，分治过程中按照横坐标从小到大排序，用树状数组维护纵坐标的信息

如果不想写CDQ分治的话可以选择二维线段树或者二维树状数组。。。但是空间消耗有点爆炸

  1. #include <cstring>
  2. #include <cstdio>
  3. #include <cmath> 
  5. inline void read(int &n)
  6. {
  7.     n=0;int w=1;register char c=getchar();
  8.     while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
  9.     while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
  10.     n*=w;
  11. }
  13. int n,m,maxy=-1;
  14. struct Query{
  15.     int type,x,y,w,aid;//w表示对查询结果贡献(+还是-)，aid是“第几个查询”
  16.     bool operator<(const Query &rhs)const
  17.     {return x==rhs.x?type<rhs.type:x<rhs.x;}
  18. }query[500001*3],emp[500001*3];
  19. int qidx,ans[500001],aidx;
  21. void addq(int type,int x,int y,int w,int aid)
  22. {query[qidx++]=(Query){type,x,y,w,aid};}
  24. inline int max(int x,int y)
  25. {return x>y?x:y;}
  27. namespace BIT
  28. {//树状数组相关
  29.     int arr[10000002];
  30.     inline int lowbit(int num)
  31.     {return num&(-num);}
  32.     void add(int idx,int val)
  33.     {
  34.         while(idx<=maxy)
  35.         {
  36.             arr[idx]+=val;
  37.             idx+=lowbit(idx);
  38.         }
  39.     }
  40.     int query(int idx)
  41.     {
  42.         int ans=0;
  43.         while(idx)
  44.         {
  45.             ans+=arr[idx];
  46.             idx-=lowbit(idx);
  47.         }
  48.         return ans;
  49.     }
  50.     void clear(int idx)
  51.     {
  52.         while(idx<=maxy)
  53.         {
  54.             if(arr[idx])
  55.                 arr[idx]=0;
  56.             else    break;
  57.             idx+=lowbit(idx);
  58.         }
  59.     }
  60. }
  62. void CDQ(int l,int r)
  63. {
  64.     if(r-l<=1)return;
  65.     int mid=l+r>>1;
  66.     CDQ(l,mid);CDQ(mid,r);
  67.     int i=l,j=mid,k=l;
  68.     while(i<mid&&j<r)
  69.     {
  70.         if(query[i]<query[j])
  71.         {
  72.             if(query[i].type==0)
  73.                 BIT::add(query[i].y,1);
  74.             emp[k++]=query[i++];
  75.         }
  76.         else
  77.         {
  78.             if(query[j].type==1)
  79.                 ans[query[j].aid]+=query[j].w*BIT::query(query[j].y);
  80.             emp[k++]=query[j++];
  81.         }
  82.     }
  83.     while(i<mid)emp[k++]=query[i++];
  84.     while(j<r)
  85.     {
  86.         if(query[j].type==1)
  87.             ans[query[j].aid]+=query[j].w*BIT::query(query[j].y);
  88.         emp[k++]=query[j++];
  89.     }
  90.     for(int i=l;i<r;++i)
  91.     {
  92.         BIT::clear(emp[i].y);//清空树状数组
  93.         query[i]=emp[i];
  94.     }
  95. }
  97. int main()
  98. {
  99.     read(n);read(m);int x,y,x1,x2,y1,y2;
  100.     while(n--)
  101.     {
  102.         read(x);read(y);
  103.         ++x;++y;//为了方便，把坐标转化为[1,1e7+1]
  104.         addq(0,x,y,0,0);maxy=max(maxy,y);//修改操作无附加信息
  105.     }
  106.     while(m--)
  107.     {
  108.         read(x1);read(y1);read(x2);read(y2);
  109.         addq(1,x1,y1,1,aidx);addq(1,x1,y2+1,-1,aidx);
  110.         addq(1,x2+1,y1,-1,aidx);addq(1,x2+1,y2+1,1,aidx);
  111.         ++aidx;maxy=max(maxy,max(y1,y2));
  112.     }
  113.     CDQ(0,qidx);
  114.     for(int i=0;i<aidx;++i)
  115.         printf("%d\n",ans[i]);
  116.     return 0;
  117. }

例题P4169 [Violet]天使玩偶/SJY摆棋子
/*
假设A为询问的点，先考虑回忆出来的点都在询问的点左下方时：

那么取到最大值时，有最小值
因此问题被转化为：对于一个询问(x,y)，找到满足时间戳在其前且的点中的最大值
*/

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cstdio>
  6. namespace inout
  7. {
  8.     const int S=1<<20;
  9.     char frd[S],*ihed=frd+S;
  10.     const char *ital=ihed;
  12.     inline char inChar()
  13.     {
  14.         if(ihed==ital)
  15.             fread(frd,1,S,stdin),ihed=frd;
  16.         return *ihed++;
  17.     }
  19.     inline int get() 
  20.     {
  21.         char ch;int res=0;bool flag=false;
  22.         while(!isdigit(ch=inChar())&&ch!='-');
  23.         (ch=='-'?flag=true:res=ch^48);
  24.         while(isdigit(ch=inChar()))
  25.             res=res*10+ch-48;
  26.         return flag?-res:res;
  27.     }
  28. };
  30. const int Maxn=0x3f3f3f3f;
  31. const int L=1e6+5;
  32. int n,m,lx,ly,rx,ry;
  33. int c[L],Ans[L];
  35. inline int min(int x,int y)
  36. {return x<y?x:y;}
  37. inline int max(int x,int y)
  38. {return x>y?x:y;}
  40. inline void Clear(int x)
  41. {
  42.     for(;x<=ly;x+=x&-x)
  43.         if(c[x])
  44.             c[x]=0;
  45.         else    break;
  46. }
  48. inline int Query(int x)
  49. {
  50.     int res=0;
  51.     for(;x;x^=x&-x)
  52.         res=max(res,c[x]);
  53.     return res;
  54. }
  56. inline void Modify(int x,int y)
  57. {
  58.     for(;x<=ly;x+=x&-x)
  59.         c[x]=max(c[x],y);
  60. }
  62. struct Ask{
  63.     int x,y,t;bool f;
  65.     Ask(){}
  66.     Ask(const int &X,const int &Y,const int &T,const bool &F):
  67.         x(X),y(Y),t(T),f(F){}
  68.     bool operator<(const Ask&a)const
  69.     {return x<=a.x;}
  70. }q[L],p[L],a[L];
  72. void CDQsolve(int l,int r)
  73. {
  74.     if(l==r)return;
  75.     int mid=l+r>>1;
  76.     CDQsolve(l,mid);CDQsolve(mid+1,r);
  78.     int j=l;
  79.     for(int i=mid+1;i<=r;++i)
  80.     if(!p[i].f)
  81.     {
  82.         for(;j<=mid&&p[j].x<=p[i].x;++j)
  83.             if(p[j].f)
  84.                 Modify(p[j].y,p[j].x+p[j].y);
  85.         int emp=Query(p[i].y);
  86.         if(emp)
  87.             Ans[p[i].t]=min(Ans[p[i].t],p[i].x+p[i].y-emp);
  88.     }
  89.     for(int i=l;i<j;++i)
  90.         if(p[i].f)
  91.             Clear(p[i].y);
  93.     std::merge(p+l,p+mid+1,p+mid+1,p+r+1,q+l);//将两个有序的序列合并成一个有序的序列，默认从小到大
  94.     for(int i=l;i<=r;++i)
  95.         p[i]=q[i];
  96. }
  98. inline void Delete()
  99. {
  100.     rx=ry=m=0;
  101.     for(int i=1;i<=n;++i)
  102.         if(!p[i].f)
  103.             rx=max(rx,p[i].x),ry=max(ry,p[i].y);
  104.     for(int i=1;i<=n;++i)
  105.         if(p[i].x<=rx&&p[i].y<=ry)
  106.             q[++m]=p[i];
  107.     for(int i=1;i<=m;++i)
  108.         p[i]=q[i];
  109. }
  111. int main()
  112. {
  113.     n=inout::get();
  114.     m=inout::get();
  115.     int k,x,y;
  116.     for(int i=1;i<=n;++i)
  117.     {
  118.         x=inout::get()+1;
  119.         y=inout::get()+1;
  120.         p[i]=Ask(x,y,i,true);
  121.         lx=max(lx,x);ly=max(ly,y);
  122.     }
  124.     while(m--)
  125.     {
  126.         k=inout::get();
  127.         x=inout::get()+1;
  128.         y=inout::get()+1;
  129.         ++n;p[n]=Ask(x,y,n,k&1);
  130.         lx=max(lx,x);ly=max(ly,y);
  131.     }
  132.     for(int i=1;i<=n;++i)a[i]=p[i];
  134.     memset(Ans,Maxn,sizeof(Ans));
  135.     ++lx;++ly;
  136.     Delete();CDQsolve(1,m);
  138.     for(int i=1;i<=n;++i)
  139.         p[i]=a[i],p[i].x=lx-p[i].x;
  140.     Delete();CDQsolve(1,m);
  142.     for(int i=1;i<=n;++i)
  143.         p[i]=a[i],p[i].y=ly-p[i].y;
  144.     Delete();CDQsolve(1,m);
  146.     for(int i=1;i<=n;++i)
  147.         p[i]=a[i],p[i].x=lx-p[i].x,p[i].y=ly-p[i].y;
  148.     Delete();CDQsolve(1,m);
  150.     for(int i=1;i<=n;++i)
  151.         if(!a[i].f)
  152.             printf("%d\n",Ans[i]);
  153.     return 0;
  154. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注