初识CDQ分治
CDQ分治是一个好东西,一直听着dalao们说所以就去学了下。
CDQ分治是我们处理各类问题的重要武器。它的优势在于可以顶替复杂的高级数据结构,而且常数比较小;缺点在于必须离线操作。 ——by __stdcall
其实CDQ分治名字听上去很高大上,其实和一般的分治没有特别大的区别,其大体流程如下:
- 将问题抽象为一个区间\([l,r]\)内的问题(废话)
- 分:将问题分解成左\([l,mid]\)右\([mid+1,r]\)两部分,然后递归操作
- 治:合并两个子问题,同时考虑到\([l,mid]\)内的修改对\([mid+1,r]\)内的查询产生的影响。即,用左边的子问题帮助解决右边的子问题。
这里特别注意CDQ分治与一般分治的区别:普通分治在合并两个子问题的过程中,左右区间内的问题不会互相影响。
经典应用——三维偏序
我们从一道模板题来看看CDQ的具体实现:
首先考虑经典的二维偏序:逆序对
这个鬼东西不是就一个归并排序or权值树状数组的事情么
我们想一下归并排序的原理,在归并的过程中(数组已经有序),那么我左边的并且坐标大于右边的坐标个数其实就是逆序对个数。
因此这也算是个简单的CDQ吧
现在我们考虑三维偏序,我们考虑先对数组总体排个序,这样在操作的过程中总有\(a_i\le a_j(i<j)\)(即使我们将区间一分为二那么右边的数的\(a_i\)始终大于左边。
然后对于第二维\(y_i\),我们考虑一下处理方法。
假设现在处理区间\([l,r]\),而此前我们已经通过递归处理好了\([l,mid]\)和\([mid+1,r]\)的答案。
那我们把\([l,mid]\)和\([mid+1,r]\)分别按\(y_i\)排个序,这样第二维也有了上面的性质。
再考虑怎么计算左边和右边的偏序关系,我们可以维护两个指针\(i,j\),每次我们将\(j\)后移一位以表示再加入一个数,此时若\(y_i\le y_j\)则不断后移\(i\),并且将\(z_i\)加入权值树状数组。
然后现在对于右边的每一个数:
- 在权值树状数组上所有的数的\(x_i\)都小于它(因为排了序)
- 在权值树状数组上所有的数的\(y_i\)都小于它(因为上面的指针偏移统计)
那么只要找\(z_i\)小于它的数个数即可,这个我们直接在树状数组上找即可。
复杂度是比较迷的\(O(n\log n)\),不过由于CQD的常数很小所以可以轻松跑过缅怀各位写树套树的dalao
下面上CODE
#include#include #include using namespace std;const int N=100005;struct data{ int x,y,z,num,sum; bool operator ==(const data &s) const { return x==s.x&&y==s.y&&z==s.z; }}a[N],q[N];int n,cnt,m,bit[N<<1],ans[N],tot;inline char tc(void){ static char fl[100000],*A=fl,*B=fl; return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;}inline void read(int &x){ x=0; char ch; int flag=1; while (!isdigit(ch=tc())) flag=ch^'-'?1:-1; while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc())); x*=flag;}inline void write(int x){ if (x>9) write(x/10); putchar(x%10+'0');}inline bool cmpx(data a,data b){ if (a.x==b.x&&a.y==b.y) return a.z >1,id=l; CDQ(l,mid); CDQ(mid+1,r); sort(q+l,q+mid+1,cmpy); sort(q+mid+1,q+r+1,cmpy); for (register int i=mid+1;i<=r;++i) { while (id<=mid&&q[id].y<=q[i].y) add(q[id].z,q[id].num),++id; q[i].sum+=get(q[i].z); } for (register int i=l;i
关于更复杂的问题
其实我也不会,不过对于一般的高维偏序,我们可以CDQ套CDQ,反正一般k维偏序用CDQ的复杂度就是\(O(n\log^{k-1} n)\)
因此维数太大时还是使用K-d tree吧