CDQ分治学习笔记

CDQ分治小结

CDQ分治，同机房的大佬看了好几天了，窝这种蒟蒻也来凑个热闹（QAQ）

引用大佬的话：

　　二维里面  ：最简单的简化版就是逆序对问题了，，可以用树状数组来维护，说他是简化版其实是因为有一维：下标已经有序了，那么就去大力♂搞

另一维就好了

　　升级版：一般的二维偏序问题：思路是一样的，要通过排序使一维有序，剩下就变成比较抽象的逆序对问题了

洛谷P1908逆序对

#include
using namespace std;
int n,cnt=0,t[500010]={0};
struct nod{
    int num,v,val;
}a[500010];
long long ans=0;
inline int read()
{
    int x=0,ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int lowbit(int x)
{
    return x&(-x);
}
void ad(int x,int y)
{
    while(x<=cnt) 
    {
        t[x]+=y;x+=lowbit(x);
    }
}
int sum(int x)
{
    int re=0;
    while(x) 
    {
        re+=t[x];
        x-=lowbit(x);
    }
    return re;
}
bool cmp(nod x,nod y)  {return x.v<y.v;}
bool comp(nod x,nod y) {return x.num<y.num;}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i].v=read(),a[i].num=i;
    sort(a+1,a+n+1,cmp);
    a[1].val=++cnt;
    for(int i=2;i<=n;i++) {if(a[i].v!=a[i-1].v) cnt++;a[i].val=cnt;}//先进行离散化，不然在洛谷的大力数据下过不去 
    sort(a+1,a+n+1,comp);//保证一维有序 
    for(int i=1;i<=n;i++)
    {
        ad(a[i].val,1); //相当于一个桶 
        ans+=i-sum(a[i].val);// 自己的位置-在自己之前小于等于自己权值的数的个数 
    }
    cout<endl;
    return 0;
}

然后才是今天的重点：：：

CDQ分治！！！（话说这种算法我曾经也yy过一部分）

CDQ分治其实主要是一种化繁为简的思想，把三维偏序问题转换为二维偏序问题

核心还是应用了二分的思想

先通过排序保证一维有序

这样的 化 话，在二分的过程中，就可以保证其中有一维是保证递增，对问题是没有影响的

说人话就是没有这一维的逆序了

这样就在二分的时候就完全不需要考虑了呢！！！

每次在二分的时候别忘记考虑左边的区间对右边的影响呢

在二分后，保证与之前有序的维度不同的一维有序就行（因为之前在有序的情况下二分的，所以左边的无论咋排序都大不过右边的）（不用证的吧）

于是在计算左区间对右区间的逆序对时候，就算它被打乱了也没有任何影响

然后用两个指针分别指向两个区间的开头，此时只比较两个区间后排序的那一维（如果早就有序的是x的话，那么它就是第y维->我本来懒得设名字来着，发现自己实在是说不明白了）

大概就是不管x了，因为x在左右区间计算贡献没有任何贡献

然后两个区间对y排序，左指针设为i，右指针设为j ，若 yj <= yi 说明在y这一维度上，存在逆序关系，不过还不敢能保证在z这个之前丝毫没管的维度上有啥子影响

所以我们就大力把z[j]加入树状数组，然后查询树状数组中有多少数小于z[i]

然后剩下一维用类似归并排序时候树状数组维护就行了

对辣别忘了清空树状数组偶

（要是我太辣鸡说的不清楚看戴马好了）

（这道模板题要求说小于等于，于是我们只能乱算一下了，在求完小于的情况下搞一下等于）

#include
using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n,_n,k,cnt[100010];
struct node
{
    int x,y,z,w,ans;
}a[100010],b[100010];
bool cmpx(node _,node __)
{
    if(_.x==__.x)
    {
        if(_.y==__.y)
            return  _.z<__.z;
        return _.y<__.y;
    }
    return _.x<__.x;
}
bool cmpy(node _,node __)
{
    return _.y==__.y ? _.z<__.z : _.y<__.y;
}
struct szsz
{
    int tr[200010],kk;
    int lowbit(int x){return (x&(-x));}
    void add(int x,int k) {for(;x<=kk;x+=lowbit(x)) tr[x]+=k;}
    int ask(int x) {int ans=0;for(;x;x-=lowbit(x)) ans+=tr[x]; return ans;}
}t;
void cdQAQ(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdQAQ(l,mid);
    cdQAQ(mid+1,r);
    sort(a+l,a+mid+1,cmpy);
    sort(a+mid+1,a+1+r,cmpy);
    int i=mid+1,j=l;
    while(i<=r)
    {
        while(a[j].y<=a[i].y&&j<=mid)
        {
            t.add(a[j].z,a[j].w);
            ++j; 
        }
        a[i].ans+=t.ask(a[i].z);
        ++i;
    }
    for(i=l; i)
    {
        t.add(a[i].z,-a[i].w);//每次完事后清空树状数组 
    }
}
int main()
{
    n=read(); k=read();
    t.kk=k;
    for(register int i=1;i<=n;++i) b[i].x=read(),b[i].y=read(),b[i].z=read();
    sort(b+1,b+1+n,cmpx);
    int tmp=0;
    for(int i=1;i<=n;++i)
    {
        tmp++; if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z)
        {
            a[++_n]=b[i]; 
            a[_n].w=tmp;
            tmp=0;
        }
    }
    cdQAQ(1,_n);
    for(int i=1; i<=_n; i++)
    {
        cnt[a[i].ans+a[i].w-1]+=a[i].w;//cnt[x]储存f[i]==x的个数，x就等于i的答案加上它重复的个数（可以取等）减去本身
    }
    for(int i=0; i)
    {
        printf("%d\n",cnt[i]);
    }
}

好辣！就是这样！有问题千万告诉我鸭！q:1154322610