mydcwfy's Blog

CDQ 分治

Posted on
Symbols count in article: 4.2k Reading time ≈ 9 mins.

同样可以使用二维树状数组。

CDQ 分治

首先我们看一下模板题：

题目传送门 Luogu

题目传送门 AcWing

1. 主要思想

我们一维一维地扩展。

1）一维

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

直接排序即可。

2）二维

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

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

也就是说，一定有 $a[j]\leq ai$。

怎样考虑优化呢？

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

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

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

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

  1. 同时在左边。
  2. 同时在右边。
  3. $j$ 在左边，$i$ 在右边。

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

左边的 $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：模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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 分治，我们可以构造三维，其中，第三维可以表示时间戳。

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

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