CDQ分治

# CDQ分治

CDQ分治大致有 3 种用法

# 解决和点对有关的问题

找到序列的重点 $mid$
将所有点对 $(i,j)$ 分成 3 类
- a. $1 \le i \le mid,1 \le j \le mid$
- b. $1\le i \le mid,mid+1 \le j \le n$
- c. $mid+1 \le i \le n,mid+1 \le j \le n$
第一类和第三类点对递归处理
设法处理第二类点对

例题：三维偏序

#include <bits/stdc++.h>
using namespace std;

struct Question {
    int id, x, y, z, cnt, ans;
    Question() : id(0), x(0), y(0), z(0), cnt(0), ans(0) {}
    Question(int id, int x, int y, int z) : id(id), x(x), y(y), z(z), cnt(0), ans(0) {}
};

struct Tree {
    int MAXN;
    vector<int> c;
    void init(int n) {
        MAXN = n + 1;
        c.resize(MAXN);
        fill(c.begin(), c.end(), 0);
    }

    void add(int x, int v) {
        for (; x < MAXN; x += x & -x) {
            c[x] += v;
        }
    }

    int get(int x) {
        int sum = 0;
        for (; x > 0; x -= x & -x) {
            sum += c[x];
        }
        return sum;
    }
};

bool cmp1(Question a, Question b) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z);
}

bool cmp2(Question a, Question b) {
    return (a.y < b.y) || (a.y == b.y && a.z < b.z);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;  cin >> n >> k;
    vector<Question> q(n + 1);
    int M = 0;
    for (int i = 1; i <= n; i++) {
        int x, y, z; cin >> x >> y >> z ;
        M = max({M, x, y, z});
        q[i] = Question(i, x, y, z);
    }
    vector<Question> qb(n + 1);
    Tree tree; tree.init(k + 1);
    int num = 0;
    sort(q.begin() + 1, q.end(), cmp1);
    for (int i = 1; i <= n; i++) {
        if (i != 1 && q[i].x == q[i - 1].x && q[i].y == q[i - 1].y && q[i].z == q[i - 1].z) {
            qb[num].cnt += 1;
        }
        else {
            num += 1;
            qb[num].x = q[i].x; qb[num].y = q[i].y; qb[num].z = q[i].z; qb[num].cnt = 1;
        }
    }

    qb.resize(num + 1);

    auto cdq = [&] (auto && cdq, int l, int r) {
        int mid = (l + r) >> 1;
        if (l == r) return;
        cdq(cdq, l, mid); cdq(cdq, mid + 1, r);

        sort(qb.begin() + l, qb.begin() + mid + 1, cmp2);
        sort(qb.begin() + mid + 1, qb.begin() + r + 1, cmp2);

        stack<int> st;
        for (int i = l, j = mid + 1; j <= r; j++) {
            while (i <= mid && qb[i].y <= qb[j].y)  {
                tree.add(qb[i].z, qb[i].cnt);
                st.push(i);
                i += 1;
            }
            qb[j].ans += tree.get(qb[j].z);
        }

        while (!st.empty()) {
            int i = st.top(); st.pop();
            tree.add(qb[i].z, -qb[i].cnt);
        }
    };

    cdq(cdq, 1, num);

    // for (int i = 1; i <= num; i++) {
    //     cout << qb[i].x << ' ' << qb[i].y << ' ' << qb[i].z << ' ' << qb[i].cnt << ' ' << qb[i].ans << '\n';
    // }

    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= num; i++) {
        ans[qb[i].ans + qb[i].cnt - 1] += qb[i].cnt;
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] << '\n';
    
    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
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

# CDQ 分治优化 1D/1D 动态规划的转移

处理这一类问题时，需要先处理 solve(l,mid)，然后处理 $l\le j \le mid,mid+1 \le j \le r$ 的点对，最后处理 solve(mid+1,r)

而三位偏序中，不需要考虑这个问题

原因是 DP 的转移必须是有序的

# 将动态问题转化为静态问题

前两种方法中，CDQ分治的目的是将序列之后递归处理点对之间的关系。这一类做法是将时间序列进行拆分

我们先递归处理 $(l,mid)(mid+1,r)$ 之间的修改-询问关系，然后处理 $l\le i \le mid,mid+1 \le j \le r$ 的修改-询问关系

注意，如果修改是非独立的话，例如赋值操作，那么第二类就要放在一三类之中，和 1D 动态规划的优化一样

上次更新: 2025/04/08, 18:03:31

← 莫队离散化→