CDQ分治学习笔记-白红宇

CDQ分治学习笔记

阅读量：6913 次

发布时间：2019-06-27

本文共 12905 字，大约阅读时间需要 43 分钟。

前言

　　CDQ是谁呢？一位与莫队，hjt一样自创算法或数据结构的大佬……

　　学习了好几天，总算对CDQ分治有了一点了解

　　CDQ真的好有用啊，特别是在三维偏序问题上

　　（那些会KD-tree和树套树的大佬就不要嘲讽我了……）

　　参考文献：

介绍

　　CDQ分治是一种非常高级的算法，码量小，常数小，可以顶替许多的数据结构，然而缺点是必须离线操作

　　一般来说，CDQ分为三个步骤：

　　1.分。将原问题划分为若干子问题，子问题间相互独立且与原问题形式相同。一般来说这些问题包含修改和查询两个操作，用区间$[l,r]$表示，将其分为$[l,mid]$和$[mid+1,r]$两个区间

　　2.治。递归解决子问题

　　3.并。将子问题合并为原问题，并考虑$[l,mid]$区间的操作对$[mid+1,r]$的操作的影响

　　然而这么叽里呱啦说了一大堆似乎没有什么用……还是详细的讲一讲好了

入门：二维偏序

　　对于一个点$(x,y)$，若存在点$(x_0,y_0)$满足$x_0>x$且$y_0>y$，则称$(x,y)<(x_0,y_0)$

　　二维偏序问题，就是给出好多个点$(x,y)$，求有多少个点大于它

　　ps：关于具体是大于还是小于，以及$x$和$y$之间的互相关系，视具体题目而定

　　实际上，逆序对就是一个二维偏序问题

　　为什么呢？我们可以把数组中的每一个点表示为$(x,y)$，其中$x$表示在数组中的位置，$y$表示权值。求逆序对个数，就是求有多少点对满足$x<x'$且$y>y'$。不就是一个二维偏序问题么？

　　逆序对个数我们是怎么求的呢？归并排序

　　回忆一下归并排序求逆序对的过程。我们每次合并两个区间的时候，要考虑左子区间对右子区间的影响。即，每次从右子区间中取出一个数时，要把“以这个数结尾的逆序对个数”加上“左子区间内比他小的数的个数”，不就是CDQ分治的过程么

　　再来考虑一般的二维偏序，对于每一个点$(x,y)$，我们可以先排序，使得$x$有序，这样，我们就可以只考虑$y$元素了（考虑一下归并排序求逆序对的过程，实际上数组的位置是默认有序的，于是我们分治的时候只需要考虑它的值就可以了）

　　如果不用归并的话，也可以用树状数组求逆序对。从左到右考虑每个点，在权值树状数组中加入，每次加入之前在树状数组中查询，看看前面有多少个数比他大就好了

　　二维偏序问题的拓展

　　给定一个N个元素的序列a，初始值全部为0，对这个序列进行以下两种操作：

　　操作1：格式为1 x k，把位置x的元素加上k（位置从1标号到N）。

　　操作2：格式为2 x y，求出区间[x,y]内所有元素的和。

　　实际上是一道树状数组的裸题（然而好死不死的非要用CDQ分治来做）

　　我们把每一个操作看成$(x,y)$，其中$x$表示操作到来的时间，$y$表示操作的点（对于查询操作，我们把它拆成$l-1$和$r$两个区间）。时间这一维是默认有序的，于是我们只要在分治的过程中将$y$这一维从小到大合并就可以了

　　那么如何表示修改和查询呢？我们在每一个操作上记录一个类型type，type为1表示修改，type为2表示被拆出来的$l-1$的区间，要对答案有一个负的贡献，type为3表示被拆出来的$r$的区间，对答案有一个正的贡献

　　因为实在懒得码了，代码是抄的

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 8 using namespace std; 9 typedef long long ll;10 const int MAXN = 500001; // 原数组大小11 const int MAXM = 500001; // 操作数量12 const int MAXQ = (MAXM<<1)+MAXN;13 14 int n,m;15 16 struct Query {17 int type, idx; ll val;18 bool operator<( const Query &rhs ) const { // 按照位置从小到大排序，修改优先于查询19 return idx == rhs.idx ? type < rhs.type : idx < rhs.idx;20 }21 }query[MAXQ];22 int qidx = 0;23 24 ll ans[MAXQ]; int aidx = 0; // 答案数组25 26 Query tmp[MAXQ]; // 归并用临时数组27 void cdq( int L, int R ) {28 if( R-L <= 1 ) return;29 int M = (L+R)>>1; cdq(L,M); cdq(M,R);30 ll sum = 0;31 int p = L, q = M, o = 0;32 while( p < M && q < R ) {33 if( query[p] < query[q] ) { // 只统计左边区间内的修改值34 if( query[p].type == 1 ) sum += query[p].val;35 tmp[o++] = query[p++];36 }37 else { // 只修改右边区间内的查询结果38 if( query[q].type == 2 ) ans[query[q].val] -= sum;39 else if( query[q].type == 3 ) ans[query[q].val] += sum;40 tmp[o++] = query[q++];41 }42 }43 while( p < M ) tmp[o++] = query[p++];44 while( q < R ) {45 if( query[q].type == 2 ) ans[query[q].val] -= sum;46 else if( query[q].type == 3 ) ans[query[q].val] += sum;47 tmp[o++] = query[q++];48 }49 for( int i = 0; i < o; ++i ) query[i+L] = tmp[i];50 }51 52 int main() {53 scanf( "%d%d", &n, &m );54 for( int i = 1; i <= n; ++i ) { // 把初始元素变为修改操作55 query[qidx].idx = i; query[qidx].type = 1;56 scanf( "%lld", &query[qidx].val ); ++qidx;57 }58 for( int i = 0; i < m; ++i ) {59 int type; scanf( "%d", &type );60 query[qidx].type = type;61 if( type == 1 ) scanf( "%d%lld", &query[qidx].idx, &query[qidx].val );62 else { // 把查询操作分为两部分63 int l,r; scanf( "%d%d", &l, &r );64 query[qidx].idx = l-1; query[qidx].val = aidx; ++qidx;65 query[qidx].type = 3; query[qidx].idx = r; query[qidx].val = aidx; ++aidx;66 }67 ++qidx;68 }69 cdq(0,qidx);70 for( int i = 0; i < aidx; ++i ) printf( "%lld\n", ans[i] );71 return 0;72 }

树状数组

基础：三维偏序

　　三维偏序是什么呢？很明显嘛，就是求有多少个点满足$x<=x',y<=y',z<=z'$

　　以模板题陌上花开为例（）

　　一般的大佬们的做法是树套树，即第一维用排序解决，第二维用权值树状数组，第三维在树状数组的每一个节点套平衡树，然而码量超大且特别难调（才不是因为我不会写才这么说呢）

　　那么考虑用CDQ如何解决

　　第一维，可以直接用排序解决，排除第一维的影响

　　那么考虑第二维和第三维如何使其变得有序呢？

　　第二维，我们可以在CDQ分治的过程中使其变得有序，那么我们要做的就是，对于两个区间，其中左区间的$x$都小于右区间的$x$，同一区间内$y$单调递增，求左边$z$小于右边$z$的有几对点

　　因为只有一维了，我们可以用上面树状数组的方法解决。从左到右考虑左区间和右区间，并记录两个指针$j$和$k$分别表示左区间和右区间，如果$a[j].y<a[k].y$，则在权值树状数组中加入$a[j].z$，否则就将$a[k]$表示的答案加上在树状数组中查询得到的比$a[k].z$小的数的个数

　　为什么这样是对的呢？因为原数组已经按第一维排序过了，所以左区间的$x$必定小于右区间，而因为左右区间分别用归并将$y$排序，所以在用两个指针扫描的时候实际是将这一区间内按$y$排序的过程，可以保证加入的$y$必然是不降的，这样的话，只要查询一下$z$即可

　　那么为什么只有左区间加入树状数组，右区间统计答案呢？因为这是归并排序，所以只有左区间对右区间的影响还没有被统计，各自区间内的影响已经被统计过，不需要再考虑了

　　顺带一提，每一次统计完之后，记得把树状数组给清空

　　时间复杂度$O(nlog^2n)$

　　依旧懒得敲代码，还是抄的

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define maxn 100010 9 #define maxk 20001010 #define ll long long 11 using namespace std;12 inline int read()13 {14 int x=0,f=1;15 char ch=getchar();16 while(isdigit(ch)==0 && ch!='-')ch=getchar();17 if(ch=='-')f=-1,ch=getchar();18 while(isdigit(ch))x=x*10+ch-'0',ch=getchar();19 return x*f;20 }21 inline void write(int x)22 {23 int f=0;char ch[20];24 if(!x){puts("0");return;}25 if(x<0){putchar('-');x=-x;}26 while(x)ch[++f]=x%10+'0',x/=10;27 while(f)putchar(ch[f--]);28 putchar('\n');29 }30 typedef struct node31 {32 int x,y,z,ans,w; 33 }stnd;34 stnd a[maxn],b[maxn];35 int n,cnt[maxk];36 int k,n_;37 bool cmpx(stnd u,stnd v)38 {39 if(u.x==v.x)40 {41 if(u.y==v.y)42 return u.z
             
              >1;64 cdq(l,mid);cdq(mid+1,r);65 sort(a+l,a+mid+1,cmpy);66 sort(a+mid+1,a+r+1,cmpy);67 int i=mid+1,j=l;68 for(;i<=r;i++)69 {70 while(a[j].y<=a[i].y && j<=mid)71 t.add(a[j].z,a[j].w),j++;72 a[i].ans+=t.ask(a[i].z);73 }74 for(i=l;i

陌上花开（CDQ+树状数组）

　　啥？你问本蒟蒻的代码？

　　弱弱的说一句，当初我做陌上花开的时候学的是某大佬的CDQ套CDQ

　　总而言之，就是先用一层CDQ把$y$值给排的有序了，然后再进一层CDQ把$z$值给排的有序，其实也能求

　　然后这代码是我自己敲的了

1 //minamoto 2 #include
      
        3 #include
       
         4 #include
        
          5 using std::sort; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 char sr[1<<21],z[20];int C=-1,Z;19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}20 inline void print(int x){21     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;22     while(z[++Z]=x%10+48,x/=10);23     while(sr[++C]=z[Z],--Z);sr[++C]='\n';24 }25 const int N=100005;26 int n,k,ans[N],d[N];27 struct node{28     int x,y,z;29     bool b;int *ans;30     inline void get(){31         x=read(),y=read(),z=read();32     }33     inline bool operator ==(const node &a)const34     {
    return x==a.x&&y==a.y&&z==a.z;}35 }a[N],b[N],c[N];36 inline bool cmp(const node &a,const node &b){37     return a.x
         
          
           
            >1;42 merge2(l,mid),merge2(mid+1,r);43 int i=l,j=l,k=mid+1,cnt=0;44 while(j<=mid&&k<=r){45 if(b[j].z<=b[k].z){46 c[i]=b[j++],cnt+=c[i].b;47 }48 else{49 c[i]=b[k++];50 if(!c[i].b) *c[i].ans+=cnt;51 }52 ++i;53 }54 while(j<=mid)55 c[i]=b[j++],++i;56 while(k<=r){57 c[i]=b[k++];58 if(!c[i].b) *c[i].ans+=cnt;59 ++i;60 }61 for(int i=l;i<=r;++i) b[i]=c[i];62 }63 void merge1(int l,int r){64 if(l==r) return;65 int mid=(l+r)>>1;66 merge1(l,mid),merge1(mid+1,r);67 int i=l,j=l,k=mid+1;68 while(j<=mid&&k<=r){69 if(a[j].y<=a[k].y){70 b[i]=a[j++],b[i].b=1;71 }72 else{73 b[i]=a[k++],b[i].b=0;74 }75 ++i;76 }77 while(j<=mid)78 b[i]=a[j++],b[i].b=1,++i;79 while(k<=r)80 b[i]=a[k++],b[i].b=0,++i;81 for(int i=l;i<=r;++i) a[i]=b[i];82 merge2(l,r);83 }84 int main(){85 //freopen("testdata.in","r",stdin);86 n=read(),k=read();87 for(int i=1;i<=n;++i)88 a[i].get(),a[i].ans=&ans[i],ans[i]=0;89 sort(a+1,a+n+1,cmp);90 for(int i=n-1;i;--i)91 if(a[i]==a[i+1]) *a[i].ans=*a[i+1].ans+1;92 merge1(1,n);93 for(int i=1;i<=n;++i) ++d[ans[i]];94 for(int i=0;i

陌上花开（CDQ套CDQ）

　　再提一嘴，理论上来说，CDQ是可以无限套下去的，也就是说不光三维偏序，四维五维六维七维都可以做。然而时间复杂度是$O(nlog^kn)$的（$k$是维数），高维的时候还不如打个暴力算了

　　三维偏序问题的拓展

　　以园丁的烦恼为例

　　平面上有N个点，每个点的横纵坐标在$[0,1e^7]$之间，有$M$个询问，每个询问为查询在指定矩形之内有多少个点，矩形用$(x1,y1,x2,y2)$的方式给出，其中$(x1,y1)$为左下角坐标，$(x2,y2)$为右上角坐标。

　　不用CDQ分治的话直接权值树状数组就可以了

　　然而CDQ应该怎么做呢？

　　我们联想到上面，把每一个点的位置变成修改，同时进行差分，把每一个询问拆成四个前缀和查询，然后不难发现每一个操作都有时间，$x$和$y$三个维度，直接用CDQ解决三维偏序问题就可以了

　　依然是抄的代码

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 9 using namespace std; 10 const int MAXN = 500001; // 点的数量 11 const int MAXM = 500001; // 询问数量 12 const int MAXQ = MAXN+(MAXM<<2); 13 const int MAXL = 10000002; // 树状数组大小 14 15 int n, m, maxy = -1; 16 17 namespace IO { // 快读相关 18 const int BUFSZ = 1e7; 19 char buf[BUFSZ]; int idx, end; 20 void init() { idx = BUFSZ; } 21 char getch() { 22 if( idx == BUFSZ ) { 23 end = fread( buf, 1, BUFSZ, stdin ); idx = 0; 24 } 25 if( idx == end ) return EOF; 26 return buf[idx++]; 27 } 28 int getint() { 29 int num = 0; char ch; 30 while( isspace(ch=getch()) ); 31 do { num = num*10 + ch-'0'; } while( isdigit(ch=getch()) ); 32 return num; 33 } 34 } 35 using IO::getint; 36 37 struct Query { 38 int type, x, y, w, aid; // w表示对查询结果贡献(+还是-)，aid是“第几个查询” 39 bool operator<( const Query &rhs ) const { 40 return x == rhs.x ? type < rhs.type : x < rhs.x; 41 } 42 }query[MAXQ]; 43 int qidx = 0; 44 void addq( int type, int x, int y, int w, int aid ) { 45 query[qidx++] = (Query){type,x,y,w,aid}; 46 } 47 48 int ans[MAXM], aidx = 0; 49 50 namespace BIT { // 树状数组相关 51 int arr[MAXL]; 52 inline int lowbit( int num ) { return num&(-num); } 53 void add( int idx, int val ) { 54 while( idx <= maxy ) { 55 arr[idx] += val; 56 idx += lowbit(idx); 57 } 58 } 59 int query( int idx ) { 60 int ans = 0; 61 while( idx ) { 62 ans += arr[idx]; 63 idx -= lowbit(idx); 64 } 65 return ans; 66 } 67 void clear( int idx ){ 68 while( idx <= maxy ) { 69 if( arr[idx] ) arr[idx] = 0; else break; 70 idx += lowbit(idx); 71 } 72 } 73 } 74 75 Query tmp[MAXQ]; 76 void cdq( int L, int R ) { 77 if( R-L <= 1 ) return; 78 int M = (L+R)>>1; cdq(L,M); cdq(M,R); 79 int p = L, q = M, o = L; 80 while( p < M && q < R ) { 81 if( query[p] < query[q] ) { 82 if( query[p].type == 0 ) BIT::add( query[p].y, 1 ); 83 tmp[o++] = query[p++]; 84 } else { 85 if( query[q].type == 1 ) ans[query[q].aid] += query[q].w * BIT::query( query[q].y ); 86 tmp[o++] = query[q++]; 87 } 88 } 89 while( p < M ) tmp[o++] = query[p++]; 90 while( q < R ) { 91 if( query[q].type == 1 ) ans[query[q].aid] += query[q].w * BIT::query( query[q].y ); 92 tmp[o++] = query[q++]; 93 } 94 for( int i = L; i < R; ++i ) { 95 BIT::clear( tmp[i].y ); // 清空树状数组 96 query[i] = tmp[i]; 97 } 98 } 99 100 int main() {101 IO::init(); n = getint(); m = getint();102 while( n-- ) {103 int x,y; x = getint(); y = getint(); ++x; ++y; // 为了方便，把坐标转化为[1,1e7+1]104 addq(0,x,y,0,0); maxy = max( maxy, y ); // 修改操作无附加信息105 }106 while( m-- ) {107 int x1,y1,x2,y2; x1 = getint(); y1 = getint(); x2 = getint(); y2 = getint(); ++x1; ++y1; ++x2; ++y2;108 addq(1,x1-1,y1-1,1,aidx); addq(1,x1-1,y2,-1,aidx); addq(1,x2,y1-1,-1,aidx); addq(1,x2,y2,1,aidx); ++aidx;109 maxy = max( maxy, max(y1,y2) );110 }111 cdq(0,qidx);112 for( int i = 0; i < aidx; ++i ) printf( "%d\n", ans[i] );113 return 0;114 }

园丁的烦恼（CDQ）

　　至于我的代码？额……我当初是直接把$y$给离散，然后排序$x$，$y$用权值树状数组解决的（我也很想知道当初为什么会这么做……）

1 //minamoto 2 #include
      
        3 #include
       
         4 #include
        
          5 using std::sort; 6 using std::unique; 7 using std::lower_bound; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 inline int read(){11     #define num ch-'0'12     char ch;bool flag=0;int res;13     while(!isdigit(ch=getc()))14     (ch=='-')&&(flag=true);15     for(res=num;isdigit(ch=getc());res=res*10+num);16     (flag)&&(res=-res);17     #undef num18     return res;19 }20 char sr[1<<21],z[20];int C=-1,Z;21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}22 inline void print(int x){23     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;24     while(z[++Z]=x%10+48,x/=10);25     while(sr[++C]=z[Z],--Z);sr[++C]='\n';26 }27 const int N=500005;28 int x[N],y[N],a[N],b[N],c[N],d[N],p[N*5];29 int n,m,tot,cnt;30 struct node{31     int x,y,id,type;32     inline void add(int a,int b,int c=0,int d=0)33     {x=a,y=b,id=c,type=d;}34     inline bool operator <(const node &b)const35     {
    return x