跳转至

CDQ 分治

泛化ψ(｀∇´)ψ

CDQ 分治的思想其实就是，考虑将贡献拆分，每次只计算跨越 \(mid\) 的贡献。

两边的贡献则是分开计算，通常来说会被应用于偏序问题以及一些动态问题的转化上。

一般来说步骤就分三步：

  1. 递归计算 \([l, mid]\) 区间的答案。
  2. 计算跨越 \(mid\) 的贡献，也就是左端点在 \([l, mid]\)，右端点在 \([mid + 1, r]\) 的贡献。
  3. 递归计算 \([mid + 1, r]\) 区间的答案。

其实这个递归计算的顺序有时候并不是那么重要，但是在 dp 优化以及一些有整体影响的动态问题上，我们必须采用这种类似“中序遍历”的顺序来解决问题。

具体的原因我们会在下面提到。

偏序问题ψ(｀∇´)ψ

这类问题也被广泛的叫做数点，因为其几何意义就是在多维空间里统计满足条件的点的个数。

给定 \(n\) 个三元组 \((a_i, b_i, c_i)\)，询问有多少对 \((i, j)\) 满足 \(j \not= i\) 且 \(a_j \le a_i, b_j \le b_i, c_j \le c_i\)。

\(1\le n \le 10^5, 1\le a_i, b_i, c_i \le 10^9\)。

二维偏序的做法是非常经典的，考虑扫描线维护一维，树状数组维护一维。

CDQ 分治解决三维偏序的思想非常暴力，通过对一维限制进行分治，去掉这个限制。

并在分治内层根据泛化中的方式，将贡献拆分成 \(O(\log n)\) 个二维偏序问题进行解决。

具体实现也不难，首先我们对 \(a\) 排序，可以看作把 \(a\) 当作下标考虑，然后对 \(a\) 这一维进行分治。

考虑设 \(\text{solve}(l, r)\) 表示算出 \([l, r]\) 区间的答案。

首先递归处理 \(\text{solve}(l, mid)\)。

然后我们考虑处理跨越 \(mid\) 的贡献，把 \(j\) 看作左端点，\(i\) 看作右端点，那么 \(a_j\) 此时一定满足 \(\le a_i\) 的条件。

我们就成功的将 \(a\) 这一维分治掉了，接下来的问题就是解决一个二维偏序了。

此时分治的两半区间内的贡献已经不再重要，也就是说我们可以随意分别调换两半区间内的顺序（因为此时我们只考虑跨越 \(mid\) 的贡献）。

于是我们对两边分别按 \(b\) 排序，维护一个形如双指针的东西，考虑每次 \(i + 1\)，令 \(j\) 不断后移加入前半区间的元素，直到加入的元素为最大的满足 \(b_j \le b_i\) 的 \(b_j\) 停止，然后此时在值域树状数组上询问 \(c_i\) 的贡献，加入答案就好，这样内层处理的复杂度就是 \(O(n \log n)\)。

那么总复杂度就是 \(O(n \log^2 n)\)。

另外在进入 \(\text{solve}(mid + 1, r)\) 之前记得清空树状数组，（这里不要暴力扫，直接打个标记之类的就好）。

有些做法在此时还会做一个归并还原，不过听 xzq 神仙说这是没有必要的，只是为了让做法更快，现在还不太能理解这个，之后做到相关题目了就来补上。

代码里的实现是后序遍历的方式，在这道题上也没啥问题。

 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;
const int inf = 0x3f3f3f3f;

struct Node {
    int a, b, c, cnt, res;
    bool operator != (const Node &rhs) const {
        if(a != rhs.a) return true;
        if(b != rhs.b) return true;
        if(c != rhs.c) return true;
        return false;
    }
} e[si], v[si];

bool cmpa(const Node &lhs, const Node &rhs) {
    if(lhs.a == rhs.a) {
        if(lhs.b == rhs.b) return lhs.c < rhs.c;
        return lhs.b < rhs.b;
    }
    return lhs.a < rhs.a;
}
bool cmpb(const Node &lhs, const Node &rhs) {
    if(lhs.b == rhs.b) return lhs.c < rhs.c;
    return lhs.b < rhs.b;
}

int n, m, V, d;
class Fenwick {
    private:
        int t[si];
        inline int lowbit(int x) { return x & -x; }
    public:
        void add(int x, int va) { while(x <= V) t[x] += va, x += lowbit(x); }
        int que(int x) { int ret = 0; while(x) ret += t[x], x -= lowbit(x); return ret; }
        void init(int n) { for(int i = 0; i <= n; ++i) t[i] = 0ll; }        
} tr;

void solve(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    sort(v + l, v + 1 + mid, cmpb);
    sort(v + 1 + mid, v + 1 + r, cmpb);
    int i = l, j = mid + 1;
    while(j <= r) {
        while(i <= mid && v[i].b <= v[j].b) {
            tr.add(v[i].c, v[i].cnt);
            ++i;
        }
        v[j].res += tr.que(v[j].c);
        ++j;
    }
    for(int k = l; k < i; ++k) 
        tr.add(v[k].c, -v[k].cnt);
}

int ans[si];
int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> d;
    for(int i = 1; i <= n; ++i) {
        cin >> e[i].a >> e[i].b >> e[i].c;
        e[i].cnt = 1, V = max(V, e[i].c);
    }
    sort(e + 1, e + 1 + n, cmpa);
    v[0] = {0, 0, 0, 0, 0};
    for(int i = 1; i <= n; ++i) {
        if(e[i] != v[m]) v[++m] = e[i];
        else v[m].cnt += 1;
    }
    solve(1, m);
    for(int i = 1; i <= m; ++i) 
        ans[v[i].res + v[i].cnt - 1] += v[i].cnt;
    for(int i = 0; i < n; ++i)
        cout << ans[i] << endl;

    return 0;
}

动静态问题的转化ψ(｀∇´)ψ

这部分的大致思想就是，如果对于一个动态问题的静态版本，它非常好实现，动态版本实现困难甚至看起来不可行，我们可以考虑离线。

然后通过 CDQ 分治将动态问题转化成一种“修改都在查询之前”的“静态问题”，这个做法也很简单，就是考虑把修改和查询看作元素，每次统计答案只统计跨过分治中心的贡献即可。

这种做法更倾向于是，将操作放在时间轴上，对操作进行时间轴分治。

一个比较经典的问题就是，矩阵加矩阵求和。

这个的静态做法就是考虑线段树+扫描线维护，但是现在问题在于，有动态操作了，我们总不可能每次修改完了重新扫描线一次吧？

所以此时考虑对操作进行时间轴分治，于是问题全部被转化为了普通的静态扫描线问题。

还有另一个经典问题是一道 Ynoi：

维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。

  1. 将区间 \([l,r]\) 的值修改为 \(x\)。
  2. 询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。

\(1\leq n , m \leq 10^5\)，\(1\leq a_i\leq 10^9\)。

仍旧是发现静态版本的问题是非常好做的，做过 HH 的项链的人都知道。

对于区间数颜色问题，我们需要维护一个 \(pre_i\) 表示 \(i\) 的同颜色前驱下标。

然后每次询问就变为了一个二维数点问题。

先考虑一个简单的带修版本，如果每次只会修改一个点，会发生什么？

很简单，\(pre\) 的变化是 \(O(1)\) 的，考虑 CDQ 分治处理时间轴，这就是一个三维偏序问题。

然后考虑区间推平怎么做，这一看就很 ODT，可以注意到插入的点不超过 \(O(m)\)。

总时间复杂度应该是 \(O(n + m)\) 的，换句话说均摊下来 \(pre\) 的变化还是 \(O(1)\) 的。

考虑维护一个原始 \(pre\) 序列上 的ODT，转换为单点修改的版本，加上足够的耐心和调试，这道题就做完了。

DP 优化ψ(｀∇´)ψ

主要来说就是决策单调性以及斜率优化的一个工具，这里不细说。

但是一个值得注意的点是，只要是 DP 转移，我们为了满足转移的正确性，一定要按照中序遍历的样子执行 CDQ 分治。

原因显然，我们不能让一个不完备的状态转移到一个新的状态，因为状态本身就是一个要求完备性的东西。

那种序列依赖于之前的修改的动态问题转静态的时候也需要注意这点。

最后更新: October 12, 2023