学习笔记——CDQ分治

雨点打透心脏的1/2处 2023-06-05 12:44 41阅读 0赞

再次感谢这位大佬的博客：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\}$肯定不行，我们可以采用归并排序的方法，对第一维从小到大进行排序，这样只会前面影响后面，然后我们再用类似于“逆序对”的方法统计第二就可以啦~~

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

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

做法：

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，不然复杂度会直线上升，只需要对于之前更新过的树状数组再反着更新回来就可以啦~

模板题：[陌上花开][Link 1]

#include<bits/stdc++.h>
    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<rhs.x;
            if(y!=rhs.y) return y<rhs.y;
            if(z!=rhs.z) return z<rhs.z;
            return id<rhs.id;
        }
        bool operator == (const node &rhs) const{
            return x==rhs.x&&y==rhs.y&&z==rhs.z;
        }
    }a[N];
    node t[N]; int tot=0;
    
    int lowbit(int x)
    {
        return x&(-x);
    }
    
    void update(int p,int x)
    {
        while(p<=k)//树状数组长度为k(值不同的个数) 
        {
            C[p]+=x;
            p+=lowbit(p);
        }
    }
    
    int query(int x)
    {
        int ret=0;
        while(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<<ans[i]<<" "; cout<<endl;
        for(int i=l;i<=mid;i++)
        {
            update(a[i].z,-a[i].cnt);
        }
        for(int i=l;i<=r;i++) a[i]=t[i];
    }
    
    int main()
    {
        memset(ans,0,sizeof(ans));
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            a[i].cnt=1;
        }
        init();
        CDQ(1,tot);
        for(int i=1;i<=tot;i++) 
        {
            ans[a[i].id]+=a[i].cnt-1;//之前枚举ans的坐标，却发现没有保存原坐标对应现坐标，但是现a[i]有对应原坐标，所以枚举a下标 
            f[ans[a[i].id]]+=a[i].cnt;//现顺序已经被归并排序弄得毫无意义，要用id，加cnt，而不是1 
        }
        for(int i=0;i<n;i++) printf("%d\n",f[i]);
        return 0;
    }

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

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

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

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

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

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

转载于:https://www.cnblogs.com/Forever-666/p/11318184.html

[CF957E]: https://codeforces.com/problemset/problem/957/E
[Link 1]: https://www.luogu.org/problem/P3810