再次感谢这位大佬的博客：https://www.cnblogs.com/ljc20020730/p/10395866.html

 

CDQ分治，是一种在分治合并中计算前面值对后面答案的贡献的一种算法。今天主要围绕多维偏序问题来对CDQ分治进行介绍

先定义偏序：（以下转载自百度百科）

设R是集合A上的一个关系，如果R是自反的、反对称的和可传递的，则称R是集合A的偏序关系，简称偏序

（1）自反性：a≤a，∀a∈P；

（2）反对称性：∀a，b∈P，若a≤b且b≤a，则a=b；

（3）传递性：∀a，b，c∈P，若a≤b且b≤c，则a≤c；

 

二维偏序：给定n个二元组，求有多少对二元组满足$a[i].x>=a[j].x$，且$a[i].y>=a[j].y$

暴力$n^{2}$肯定不行，我们可以采用归并排序的方法，对第一维从小到大进行排序，这样只会前面影响后面，然后我们再用类似于“逆序对”的方法统计第二就可以啦~~

拓展题：（怎么用二维偏序自己想哦~）

 

三位偏序：和二维偏序类似，在用逆序对维护第二维的同时，我们需要再用数据结构统计一下同时满足第三维时的贡献

做法：

1.对第一维进行排序

2.对二维进行归并排序，并同时统计前面对后面的贡献（在同一组的之前已经统计过了）：

3.若前面$a[i].y$一直小于等于$a[j].y$，则将$a[i].z$塞到树状数组里维护：即这个这段区间内值为$z$的有几个（记得对于$z$离散化）

4.一旦$a[i]>a[j]$就说明后面的$a[i]$不会再对$a[j]$产生贡献，所以对于$a[j].z$在树状数组$[1,a[j].z]$区间内查询有多少个$z$即为贡献

代码实现：（细节超多啊QAQ）

首先是要去重，因为完全相同的三元组是会互相影响的，而在归并排序中只会左边影响右边，会少讨论情况

其次是在统计答案时每几个完全相同的三元组的内部影响要加上

还有就是在树状数组用完以后要清0，但不要用memset，不然复杂度会直线上升，只需要对于之前更新过的树状数组再反着更新回来就可以啦~

模板题：

#include
     
      using namespace std;const int N=102000;void print(){    puts("OK");}int n,tt[N],ans[N],f[N],k;int C[N*2];struct node{    int x,y,z,id,cnt;    bool operator < (const node &rhs) const{        if(x!=rhs.x) return x
      
       0)    {        ret+=C[x];        x-=lowbit(x);    }    return ret;}void init(){    sort(a+1,a+n+1);    int i=1; tot=0;    while(i<=n)    {        int j=i+1;        while(j<=n&&a[j]==a[i]) j++;        t[++tot]=a[i];        t[tot].cnt=j-i;        t[tot].id=tot;            i=j;    }    for(int i=1;i<=tot;i++) a[i]=t[i];    for(int i=1;i<=tot;i++) tt[i]=a[i].z;    sort(tt+1,tt+tot+1);    int m=unique(tt+1,tt+tot+1)-tt-1;    for(int i=1;i<=tot;i++)    {        a[i].z=lower_bound(tt+1,tt+m+1,a[i].z)-tt;        //记得要算自己内部的影响     }}void CDQ(int l,int r){    if(l==r) return;    int mid=(l+r)>>1;    CDQ(l,mid);     CDQ(mid+1,r);    int i=l,j=mid+1,top=l-1;    while(i<=mid&&j<=r)    {        if(a[i].y<=a[j].y)//能做出贡献         {            update(a[i].z,a[i].cnt);            t[++top]=a[i++];        }        else        {            ans[a[j].id]+=query(a[j].z);//之前j写成i了             t[++top]=a[j++];        }    }    while(i<=mid)    {        update(a[i].z,a[i].cnt);        t[++top]=a[i];        i++;    }    while(j<=r)    {        ans[a[j].id]+=query(a[j].z);        t[++top]=a[j];        j++;    }    //for(int i=1;i<=tot;i++) cout<
       
        <<" "; cout<
       
      
     

 

四维偏序：这是神仙题啊~~~一般用bitset解决，CDQ套CDQ复杂度实在是太大了，但还是介绍一下思路吧

首先第一维还是排序，然后对第二位进行CDQ分治，但是还剩下两维（可以每一次插入都把后三位拉出来进行cdq，但复杂度太高了，我们考虑在最后进行）

因为只有前面对后面有影响，所以我们记录它是在左边还是在右边

显然在归并排序之后第二维已经达到了有序，然后我们再来一遍CDQ，对记录是左边的进行update，右边的进行query，而且因为从第二维小到大排序，所以一定只有前面影响后面

最后就是再对第三位进行分治，然后对第四维进行树状数组统计就可以啦~~

（代码详见上述那位神仙的博客，本蒟蒻没有这个实力啊QAQ）