简介

CDQ 分治解决三维偏序问题，在接触它之前，先来看一下二维偏序问题。

Stars（二维偏序）

给定 n 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

题目链接：LOJ 10114。

对于这种问题，可以按照字典序排序，然后可以用归并排序的分治算法或者树状数组解决这个问题。这里已经按照 Y,X 字典序排好序了，并且保证没有重复的点，所以我们只需要读入 X 即可。

树状数组

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 15010, M = 35010;
int n, ans[N], tr[M];

#define lowbit(x) ((x)&(-x))

void add(int p, int v) {
    for (; p < M; p += lowbit(p))
        tr[p] += v;
}

int query(int p) {
    int res = 0;
    for (; p; p -= lowbit(p))
        res += tr[p];
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d%*d", &x);
        // x 有可能为 0 这使 add 时死循环
        ++x;
        ans[query(x)]++;
        add(x, 1);
    }
    for (int i = 0; i < n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

归并排序

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 15010;
int n, ans[N];
struct Data {
    int x, res;
} q[N], tmp[N];

void mergesort(int l, int r) {
    if (l >= r) return;
    int mid = l+r >> 1;
    mergesort(l, mid), mergesort(mid+1, r);
    
    int k = 0, i = l, j = mid+1;
    while (i <= mid && j <= r) {
        if (q[i].x <= q[j].x) tmp[k++] = q[i++];
        // l ~ i-1 都满足性质
        else q[j].res += i-l, tmp[k++] = q[j++];
    }
    
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) q[j].res += i-l, tmp[k++] = q[j++];
    
    k = 0;
    for (i = l; i <= r; i++) q[i] = tmp[k++];
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%*d", &q[i].x);
    
    mergesort(0, n-1);
    
    for (int i = 0; i < n; i++) ans[q[i].res]++;
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
   
    return 0;
}

三维偏序

有 nn 个元素，第 ii 个元素有 ai,bi,cia_i,b_i,c_i 三个属性，设 f(i)f(i) 表示满足 aj≤aia_j \leq a_i 且 bj≤bib_j \leq b_i 且 cj≤cic_j \leq c_i 且 j≠ij \ne i 的 jj 的数量。

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

题目链接：AcWing 2815，P3810。

我们需要将二维偏序中的两种思路结合起来，就能解决三维偏序问题，这也是 CDQ 分治的模板。

在此之前，我们需要手动实现一个类似 std::unique 的去重函数，并且能统计出来每个元素出现了多少次，大概长下面这样：

1
2
3
4
5
6
7
8
9
10
11
// q[i].s should be 1 at first
template <typename T>
int unique1(T q[], int n) {
    int k = 1;
    sort(q, q+n);
    for (int i = 1; i < n; i++) {
        if (q[i] == q[k-1]) q[k-1].s ++;
        else q[k++] = q[i];
    }
    return k;
}

但是，其实我们可以用 set 解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//  q[i].s should be 1 at first
template <typename T>
int unique2(T q[], int n) {
    set<T> S;
    for (int i = 0; i < n; i++) {
        const auto& it = S.find(q[i]);
        if (it == S.end()) S.insert(q[i]);
        else {
            T t = *it;
            t.s = it->s + 1;
            S.erase(it), S.insert(t);
        }
    }
    int k = 0;
    for (auto& t: S) {
        q[k++] = t;
    }
    return k;
}

复杂度显然都是 O(nlog⁡n)O(n\log n)，而且肯定是上面那种写法常数小，实测能快一倍。

很显然，对于相同的元素，它们是满足偏序性质的，所以最终一个元素的偏序值是计算出来的结果加上 s−1s-1，其中 ss 代表与它相同的元素的数量（包括它自己）。

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100010, M = 200010;
int n, ans[N], tr[M];

struct Data {
    int a, b, c, s, res;
    
    bool operator<(const Data& d) const {
        if (a != d.a) return a < d.a;
        if (b != d.b) return b < d.b;
        return c < d.c;
    }
    
    bool operator==(const Data& d) const {
        return a == d.a && b == d.b && c == d.c;
    }
} q[N], tmp[N];

#define lowbit(x) ((x)&(-x))

void add(int p, int v) {
    for (; p < M; p += lowbit(p))
        tr[p] += v;
}

int query(int p) {
    int res = 0;
    for (; p; p -= lowbit(p))
        res += tr[p];
    return res;
}

void mergesort(int l, int r) {
    if (l >= r) return;
    
    int mid = l+r >> 1;
    mergesort(l, mid), mergesort(mid+1, r);
    
    int i = l, j = mid+1;
    int k = 0;
    while (i <= mid && j <= r) {
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), tmp[k++] = q[i++];
        else q[j].res += query(q[j].c), tmp[k++] = q[j++];
    }
    while (i <= mid) add(q[i].c, q[i].s), tmp[k++] = q[i++];
    while (j <= r) q[j].res += query(q[j].c), tmp[k++] = q[j++];
    // 清空树状数组 不要用 memset 巨慢
    for (i = l; i <= mid; i++) add(q[i].c, -q[i].s);
    for (i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k];
}

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

[CQOI 2017] 老C的任务

给定 nn 个点，每个点 (x,y,p)(x,y,p)，再给 mm 个查询，每次查询 (x1,y1)∼(x2,y2)(x_1,y_1)\sim(x_2,y_2) 区域内所有点的 pp 之和。

题目链接：AcWing 2487，P3755。

对于在 CDQ 分治中的 zz 坐标，令点 z=0z=0，查询 z=1z=1

这里用前缀和的思想，每个查询存四个点，所以这就要存一下在统计答案的时候应该加还是减了，用一个 sgn 表示符号。

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
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 500010;

struct Data {
    int x, y, z, p, sgn, id;
    LL res;
    
    bool operator<(const Data& d) {
        if (x != d.x) return x < d.x;
        if (y != d.y) return y < d.y;
        return z < d.z;
    }
} q[N], tmp[N];
LL ans[N];

int n, m;

void mergesort(int l, int r) {
    if (l >= r) return;
    int mid = l+r >> 1;
    mergesort(l, mid), mergesort(mid+1, r);
    
    int k = 0, i = l, j = mid+1;
    LL res = 0;
    
    while (i <= mid && j <= r) {
        if (q[i].y <= q[j].y) res += q[i].p, tmp[k++] = q[i++];
        else q[j].res += res, tmp[k++] = q[j++];
    }
    
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) q[j].res += res, tmp[k++] = q[j++];
    
    for (i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, y, p;
        scanf("%d%d%d", &x, &y, &p);
        q[i] = {x, y, 0, p};
    }
    int k = n;
    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        q[k++] = {x2, y2, 1, 0, 1, i};
        q[k++] = {x1-1, y1-1, 1, 0, 1, i};
        q[k++] = {x2, y1-1, 1, 0, -1, i};
        q[k++] = {x1-1, y2, 1, 0, -1, i};
    }
    sort(q, q+k);
    mergesort(0, k-1);
    
    for (int i = 0; i < k; i++)
        if (q[i].z) ans[q[i].id] += q[i].res * q[i].sgn;
    
    for (int i = 0; i < m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

[CQOI 2011] 动态逆序对（待补）