文章总览：盐与犬

豪德，失踪多年的我终于回来写文章了（什么？你说我干什么了？你怎么知道我出遐蝶了！），，，言归正传，这篇文章的内容是 CDQ 分治，最近做到了一道关于 CDQ 分治的题目，一看就发现不会，所以这篇文章来讲一下 CDQ 分治的一些基本原理与应用，所谓 CDQ 分治，更广泛的来说是一种思想，它在被提出之前就已经广泛流传于各大巨佬之间，后来被高中的 IOI2008 金牌得主陈丹琦总结，因此而得名。

话说这剧情怎么这么熟悉，上次讲莫队的时候好像和这个剧本完全一样

下为本文大纲：

  1. 二维数点问题的规律总结
  2. CDQ分治思想的简单推导
  3. CDQ分治模板题讲解
  4. CDQ分治的简单应用

前情回顾：狮子之尾

友情链接：

【算法介绍】二维数点 | 祝馀宫
【算法介绍】扫描线思想 | 祝馀宫

上面这两篇是我曾经结下的关于二维数点的一些文章。我们可以简单的总结一下，从最最开始的一维数点，是如何一步一步拓展到二维数点的呢？

首先来从一维数点讲起，这应该是数点问题的起源。什么是数点？举个例子，现在我有一个一维的数轴，我往上面标点，标了点以后，查询某一区间，或者某一前缀等等等等有多少个点。这就是一维数点问题。

这里就需要区分了，就是一些问题他是在线的呢，还是离线的。这是区分大多数算法的重要指标。举个例子，如果我们的操作即“插入”和“查询”，如果在我的问题中，插入和查询时交织的，就是在两次“查询”操作之间存在“插入”操作，这就是在线问题。反之，如果“插入”操作是存在于某一前缀，即前半部分全是插入，后半部分全是查询，这就是离线问题。一般来说，我们处理离线问题的手段多且优与在线操作。

那么在线和离线能否转化呢？可以的，比如说我们学过的转化在线至离线的算法，比如说莫队，它的思想就是从一个小点开始扩展，然后缩小，锁定了一个查询以后得到答案，保存到数组里，最终统一输出。

那么一维数点的常见手段是什么呢？不论是在线还是离线，一维数点永远是最有手段的罢。不论是在线我们用树状数组啊，线段树啊等等等等之类的数据结构；还是离线算法类似于差分啊，前缀和啊之类的。而且基本来说复杂度都不算特别劣，是一类比较好处理的问题。

二维数点就是另外一种思路了。一般来说，二维数点的常规思路有两类。第一种是排序消耗一维度，然后退化成一维数点的问题来处理，这种做法一般是属于离线的。另外来说，如果强制在线的话，我们也可以拓展为二维树状数组来搞定，这样就是在线的。

可以注意到的是，一维数点及其好解决，所以二维数点采用了排序的方式，使得问题退化为一维数点问题，这是非常常用的一种思想，那么这种思想是否可以拓展到三维数点呢？

算法推导：逝者的新生

显然是可以的。那么接下来关于三维数点的问题，那么还是一样的，我们可以简单的考虑一下。如果是借用上面的思路，我们首先排序一维度，那么问题就转化为了二维数点，而这个二维数点该如何处理呢？如果说是二维树状数组，那就让人大跌眼镜。毕竟二维树状数组的时间复杂度虽然是 $O(n\log^2 n)$ 还算过关，但空间复杂度可以高达 $O(n^2)$，跑不了一点，那么这时候该怎么办呢？

我们可以从一个最最经典的双关键字的问题开始考虑：逆序对。为什么说是逆序对呢？可以想一下，逆序对有两个关键字，第一个是下标，另一个是数值，所谓逆序对的数量，就是对于一个序列中下表满足 $ia[j]$，那么这就是一组逆序对。如果我们把下标看作横轴，数值看作纵轴，那么其实就是一个二维数点问题，我们要寻找一个点左上角有多少个点。

回忆一下逆序对是如何解决的。我们用了归并排序，因为下表默认就是有序的，所以说我们归并排序的时候就有一个 $ i\lt j $ 的特有条件。 那么接下来的需求就是计算有多少满足 $a[i]>a[j]$ 了，这其实是一个一维的问题，并且在实现中我们用了非常简单的一个式子就解决了，这也让这个算法的复杂度是归并排序的复杂度即 $O(n\log n)$。

这个思路是否可以拓展到三维呢？可以的。如果我们排序了以后，归并一手，左右自动处理，那么问题就变成如何快速合并左右了，这是递归问题的思考方向。而我们会发现合并左右其实就是一个二维数点的问题，二维数点的问题我们就可以处理了，比如说扫描线+一维树状数组之类的，这里说的扫描线其实就是从第一位开始，往后划动，每一次记录线上的点到树状数组里，不难算出这样的复杂度是 $O(n\log ^2 n)$ 但复杂度基本上是 $O(n)$ 级别的。

基本上这就是 CDQ 分治基本的思想了，我们来看一道模板题感受一波。

算法模板：临终的轻语

P3810 【模板】三维偏序（陌上花开） - 洛谷

题目大意

有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。

对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。

解题思路

很简单，这一看就是非常明显的三维数点问题（好像更多叫做三位偏序）我们排序一维度以后把剩下的归并，归并以第二维为第一关键字，这过程中计算小于等于该点的第三维，用树状数组维护。非常大好理解，题目给出的点需要去重，并统计数量，不然的话无法在一个位置维护多个点。

正确代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

template<class T, const int N>
class BIT {
public : 
    T c[N]; int size;
    inline int lowbit(int x) { return x&(-x); }
    inline void init(int sz) {
        size = sz;
        for(int i = 1; i <= sz; i++) c[i] = 0;
    }
    inline void modify(int x, T v) {
        assert(x != 0);
        for(int i = x; i <= size; i += lowbit(i))
            c[i] += v;
    }
    inline T query(int x) {
        assert(x <= size); T ans = 0;
        for(int i = x; i; i -= lowbit(i))
            ans += c[i];
        return ans;
    }
};

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

int n, K;
struct Node {
    int x, y, z, ans;
    inline bool operator == (const Node & b) const {
        return x == b.x && y == b.y && z == b.z;
    }
    inline bool operator < (const Node & b) const {
        if(x != b.x) return x < b.x;
        if(y != b.y) return y < b.y;
        return z < b.z;
    }
}a[N];
map<Node , int >cnt;

inline void Input() {
    read(n, K);
    for(int i = 1; i <= n; i++) {
        read(a[i].x, a[i].y, a[i].z);
        cnt[a[i]]++;
    }
}

BIT<int , M >c;
Node tmp[N];

inline 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, k = l;
    while(i <= mid || j <= r) {
        if(j > r || (i <= mid && make_pair(a[i].y, a[i].z) <= make_pair(a[j].y, a[j].z))) {
            c.modify(a[i].z, cnt[a[i]]);
            tmp[k++] = a[i++];
        }
        else {
            a[j].ans += c.query(a[j].z);
            tmp[k++] = a[j++];
        }
    }
    for(int i = l; i <= mid; i++) c.modify(a[i].z, -cnt[a[i]]);
    for(int i = l; i <= r; i++) a[i] = tmp[i];
}

int tot[N];

inline void Work() {
    c.init(K);
    sort(a + 1, a + n + 1);
    int t = unique(a + 1, a + n + 1) - a - 1;
    CDQ(1, t);
    for(int i = 1; i <= t; i++) {
        tot[a[i].ans + cnt[a[i]] - 1] += cnt[a[i]];
    }
    for(int i = 0; i < n; i++) {
        printf("%d\n", tot[i]);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

算法应用：午后之死

这基本算是 CDQ 分治最最基本的应用题目了，接下来看个熟悉的问题，动态逆序对。这个问题好像是不止一次做了，我印象里至少使用过主席树做过的出门右转：

友情链接：

【算法介绍】可持久化相关数据结构 - 带修可持久化线段树 | 祝馀宫

重温一手题面：

题目大意

对于序列 $a$，它的逆序对数定义为集合

中的元素个数。

现在给出 $1\sim n$ 的一个排列，按照某种顺序依次删除 $m$ 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

解题思路

这是在线的做法，那么如果是离线，这道题这么做呢？上面就讲过了，事实上逆序对就是一个二维的数点问题，那么这时候动态逆序对相对于这个静态的逆序对是多了什么元素呢？显然的，多了一个时间轴。那么这一个时间轴就相当于是我们多出来的一个信息，所以说我们可以随便指定一个轴，开始 CDQ 分治。

问题显然可以抽象为三个约数：

  1. $time_i>time_j$：因为这个要满足访问的时候还没被删掉。
  2. $pos_i>pos_j$：这是逆序对的定义。
  3. $val_i<val_j$：这是逆序对的定义。

CDQ 分治的灵活性也在这里体现出来了，你可以指定任何的轴为要分支的，但是万变不离其宗，这里我把它看成了倒着一个一个添加点，所以需要修改一下刚刚的约数，不过无伤大雅。

正确代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 150010;

namespace FastIO {
    template<typename T> inline void read(T &x) {
        x = 0;
        int f = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            x = x * 10 + (ch ^ 48);
            ch = getchar();
        }
        x *= f;
        return;
    }
    template<typename T, typename... Args> inline void read(T &x, Args &...args) {
        read(x);
        read(args...);
    }
};
using namespace FastIO;

template<class T, const int S>
struct BIT {
    T c[S];
    int size;
    inline int lowbit(int x) { return x & (-x); }
    void init(int sz) {
        size = sz;
        memset(c, 0, sizeof(c));
    }
    void modify(int x, T v) {
        for (; x <= size; x += lowbit(x)) c[x] += v;
    }
    T query(int x) {
        T res = 0;
        for (; x; x -= lowbit(x)) res += c[x];
        return res;
    }
};

int n, m;
struct Node {
    int z, x, y;
    Node() {}
    Node(int t, int x_, int y_) : z(t), x(x_), y(y_) {}
    inline bool operator < (const Node &b) const {
        return x == b.x ? y < b.y : x < b.x;
    }
} A[N], tmp[N];
int pos[N];
ll Ans[N];

BIT<int, N> c;

inline void Input() {
    read(n, m);
    c.init(n);
    for (int i = 1, x; i <= n; ++i) {
        read(x);
        pos[x] = i;
        A[i] = Node(0, i, x);
    }
    int tim = n;
    for (int i = 1, x; i <= m; ++i) {
        read(x);
        A[pos[x]].z = tim--;
    }
    for (int i = 1; i <= n; ++i) {
        if (!A[i].z) A[i].z = tim--;
    }
}

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, k = l;
    while(i <= mid || j <= r) {
        if(j > r || (i <= mid && A[i] < A[j])) {
            c.modify(A[i].y, 1);
            tmp[k++] = A[i++];
        } 
        else {
            Ans[A[j].z] += c.query(c.size) - c.query(A[j].y);
            tmp[k++] = A[j++];
        }
    }
    for(int i = l; i <= mid; i++) c.modify(A[i].y, -1);
    for(int i = l; i <= r; i++) A[i] = tmp[i];
    for(int i = r; i >= l; i--) {
        if(A[i].z <= mid) {
            c.modify(A[i].y, 1);
        } 
        else {
            Ans[A[i].z] += c.query(A[i].y);
        }
    }
    for(int i = l; i <= r; i++) {
        if(A[i].z <= mid) {
            c.modify(A[i].y, -1);
        }
    }
}

inline void Work() {
    sort(A + 1, A + n + 1, [](Node &a, Node &b) { 
        return a.z < b.z; 
    });
    CDQ(1, n);
    for(int i = 1; i <= n; i++) {
        Ans[i] += Ans[i - 1];
    }
    for(int i = n; i >= n - m + 1; i--) {
        printf("%lld\n", Ans[i]);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

算法实战：血与沙

查看相关算法标签喵！

参考资料（以下排名不分先后）