CDQ 分治

· · 个人记录

CDQ 分治

首先我们看一下模板题：

题目传送门 Luogu

题目传送门 AcWing

1. 主要思想

我们一维一维地扩展。

1）一维

首先，我们考虑只有一维的。

直接排序即可。

2）二维

然后，我们考虑有二维的。

首先，我们按双关键字排序，然后从前往后一个一个枚举，在 i 前面才可能会有答案。

也就是说，一定有 a[j]\leq a[i](j<i)。

怎样考虑优化呢？

我们可以先对 b[] 进行离散化，然后再利用树状数组就可以解决了。

时间复杂度为 O(n\log n)。

另外，我们可以使用分治。

假设 j 对 i 满足条件，有三种情况：

  1. 同时在左边。
  2. 同时在右边。

对于前两种情况，我们可以进行递归。

左边的 a 一定小于等于右边的 a，于是我们就可以只考虑 b。

考虑与求逆序对类似的算法。

首先，我们按 a 进行排序，然后归并计算答案时按 b 进行排序。

对于每一个区间，我们按 b 进行归并排序，在右边的 i 使用双指针算法就可以计算了。

由于本身就是一个归并排序的过程，我们无需整个排序，只需归并即可。

时间复杂度为 O(n\log n)。

3）三维

即本题。

首先，我们按照三关键字排序。

那么，j 只有在 i 的左边，才可能对 i 满足条件。

还是按照二维的分治算法，我们可以二分区间。

当 j 在左，i 在右时，我们可以对于每一个区间按 b 进行归并排序。

对于每一个 i，我们可以二分找到最后一个小于等于 b_i 的 j，在利用二维的树状数组算法，我们就可以找到 j 之前小于等于 c_i 的值。

每一层都是 O(n\log n)，其中枚举每一个为 O(n)，二分和树状数组为 O(\log n)，在有 \log n 层，总复杂度为 O(n\log^2 n)。

4）注意事项

我们不得不处理两个数据完全相同的情况，因为枚举 i，它后面的相同的就不会枚举到，所以要去重。

2. 例题

T1：模板题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lowbit(x) (x&-x)
using namespace std;

const int N=1e5+10,M=2e5+10;

struct Node{
    int a,b,c,sz,res;
    const bool operator <(const Node &t)const{
        if (a!=t.a) return a<t.a;
        if (b!=t.b) return b<t.b;
        return c<t.c;
    }
    const bool operator ==(const Node &t)const{
        return a==t.a&&b==t.b&&c==t.c;
    }
}k[N],tmp[N];

int tr[M],ans[N],n,m;

void add(int x,int c)
{
    for (int i=x;i<M;i+=lowbit(i)) tr[i]+=c;
}

int ask(int x)
{
    int res=0;
    for (int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

void merge_sort(int l,int r)
{
    if (l==r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);merge_sort(mid+1,r);
    int j=l,i=mid+1,h=0;
    while (j<=mid&&i<=r)
        if (k[j].b<=k[i].b) add(k[j].c,k[j].sz),tmp[h++]=k[j++];
        else k[i].res+=ask(k[i].c),tmp[h++]=k[i++];
    while (j<=mid) add(k[j].c,k[j].sz),tmp[h++]=k[j++];
    while (i<=r) k[i].res+=ask(k[i].c),tmp[h++]=k[i++];
    for (int i=l;i<=mid;++i) add(k[i].c,-k[i].sz);
    for (int now=0,i=l;now<h;++i,++now) k[i]=tmp[now];
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0,a,b,c;i<n;++i)
    {
        scanf("%d %d %d",&a,&b,&c);
        k[i]=(Node){a,b,c,1,0};
    }
    sort(k,k+n);
    int now=1;
    for (int i=1;i<n;++i)
        if (k[now-1]==k[i]) k[now-1].sz++;
        else k[now++]=k[i];
    merge_sort(0,now-1);
    for (int i=0;i<now;++i)
        ans[k[i].res+k[i].sz-1]+=k[i].sz;
    for (int i=0;i<n;++i) printf("%d\n",ans[i]);
    return 0;
}

T2：[CQOI2017]老C的任务

题目传送门 Luogu

题目传送门 AcWing

首先，我们可以转化为二维前缀和，问题就转化为了 x\leq x_{now},y\leq y_{now} 的所有 p 之和。

如果是在线，可能就会超时，我们使用离线算法。

将查询的点记为 1，原来的点记为 0。

那么，我们就相当于 x\leq x_{now},y\leq y_{now}, z< z_{now} 的点。

由于 z 只有 0 和 1，直接无需树状数组，复杂度 O(n\log n)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=5e5+10;

struct Node{
    int a,b,c,id,f,p;
    ll sum;
    const bool operator <(const Node &t){
        if (a!=t.a) return a<t.a;
        if (b!=t.b) return b<t.b;
        return c<t.c;
    }
}k[N],tmp[N];

int n,m;
ll ans[N];

void merge_sort(int l,int r)
{
    if (l==r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);merge_sort(mid+1,r);
    int j=l,i=mid+1,h=0;
    ll sum=0;
    while (j<=mid&&i<=r)
        if (k[j].b<=k[i].b) sum+=(!k[j].c)*k[j].p,tmp[h++]=k[j++];
        else k[i].sum+=sum,tmp[h++]=k[i++];
    while (j<=mid) tmp[h++]=k[j++];
    while (i<=r) k[i].sum+=sum,tmp[h++]=k[i++];
    for (int i=l,t=0;t<h;++t,++i) k[i]=tmp[t];
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=0,a,b,c;i<n;++i)
    {
        scanf("%d %d %d",&a,&b,&c);
        k[i]=(Node){a,b,0,0,0,c,0};
    }
    int tot=n;
    for (int i=0,a,b,c,d;i<m;++i)
    {
        scanf("%d %d %d %d",&a,&b,&c,&d);
        k[tot++]=(Node){a-1,b-1,1,i,1,0,0};
        k[tot++]=(Node){a-1,d,1,i,-1,0,0};
        k[tot++]=(Node){c,d,1,i,1,0,0};
        k[tot++]=(Node){c,b-1,1,i,-1,0,0};
    }

    sort(k,k+tot);
    merge_sort(0,tot-1);

    for (int i=0;i<tot;++i)
        if (k[i].c) ans[k[i].id]+=k[i].sum*k[i].f;
    for (int i=0;i<n;++i) printf("%lld\n",ans[i]);
    return 0;
}

T3：[CQOI2011]动态逆序对

题目传送门 Luogu

题目传送门 AcWing

其实，使用 CDQ 分治，我们可以构造三维，其中，第三维可以表示时间戳。

例如本题，我们可以用第三维表示被删除的时间。

如果有未被删除的数，把时间戳设为大于总删除数即可。