今天是布灵布灵的魔法宝狈！

笑死演都不演了我就是为了新封面才写的笔记（

概述

CDQ分治指代一类算法思想，由IOI2008金牌得主陈丹琦在高中时整理并总结，因此得名。

CDQ分治主要用来处理点对之间的某些贡献问题，若某些贡献具有传递性，则可以用来优化DP，或处理k维偏序问题。同时，如果把时间前后也看作一个维度，那么我们可以把一些动态操作离线，当做静态问题进行处理。所以CDQ分治非常妙，相对而言用途比较广泛。

在现代算法竞赛语境中，CDQ分治一般指特殊的归并分治，即不使用原先的归并操作，而借助一些高级数据结构（一般都是树状数组）来进行某些信息的统计。不过这个定义也并不绝对，某些情况下CDQ分治仅仅指代这一类分治思想，不使用高级数据结构也可以称作CDQ分治（例如CDQ套CDQ解决三维偏序问题，内层CDQ仅使用普通归并，但仍称CDQ）。

具体算法流程如下：我们定义一个函数$CDQ(l,r)$，计算区间$[l,r]$内的所有点对之间的贡献。取其中点$mid=(l+r)/2$，把区间内所有点分成左右两部分，我们递归处理左右两部分的点对内部的贡献，再设法计算左边部分和右边部分之间的贡献。可以看到除了计算两部分之间相互的贡献之外都是模板代码，这一部分的贡献的计算方式则需要额外设计算法来解决。

例题

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

很经典的题目，八仙过海各显神通，KDTree，bitset都可做，但我们今天的主角是CDQ分治。

CDQ分治之前先按第一维排序消掉一维，分治处理完左右两部分保证左右两部分按照第二维有序，此时虽然两部分内部的第一维可能会乱，但整体而言，左边部分的第一维依然不大于右边部分的第一维。我们使用双指针控制住第二维，使用树状数组统计第三维的贡献即可。分析时间复杂度，$T(n)=2T(n/2)+O(n\log{n})$，根据主定理得 $T(n)=O(n{\log^{2}{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
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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct {
    int a, b, c, ans, cnt;
} s1[N], s2[N];
int ans[N];
int t[N];
int n, k;

void add(int x, int v) {
    while (x <= k) {
        t[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l;
    for (int i = mid + 1; i <= r; ++i) {
        while (j <= mid && s2[j].b <= s2[i].b) {
            add(s2[j].c, s2[j].cnt);
            j++;
        }
        s2[i].ans += query(s2[i].c);
    }
    for (int i = l; i < j; ++i) {
        add(s2[i].c, -s2[i].cnt);
    }
    sort(s2 + l, s2 + r + 1, [&](auto x, auto y) {
        if (x.b != y.b) return x.b < y.b;
        return x.c < y.c;
    });
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        auto& [a, b, c, ans, cnt] = s1[i];
        cin >> a >> b >> c;
    }
    sort(s1 + 1, s1 + n + 1, [&](auto x, auto y) {
        if (x.a != y.a) return x.a < y.a;
        if (x.b != y.b) return x.b < y.b;
        return x.c < y.c;
    });
    int m = 0;
    for (int i = 1, cnt = 0; i <= n; ++i) {
        cnt++;
        if (s1[i].a != s1[i + 1].a || s1[i].b != s1[i + 1].b || s1[i].c != s1[i + 1].c) {
            s2[++m] = s1[i];
            s2[m].cnt = cnt;
            cnt = 0;
        }
    }
    cdq(1, m);
    for (int i = 1; i <= m; ++i) {
        ans[s2[i].ans + s2[i].cnt - 1] += s2[i].cnt;
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

此处是普通的CDQ内部使用BIT的写法，后文介绍CDQ套CDQ的时候给出了本题的第二种写法，敬请留意。

P3157 [CQOI2011] 动态逆序对

带单点修改询问每次修改前序列总逆序对数量。

逆序对本质上是二维偏序问题，如前文所述，我们将时间也看作一个维度，当做三维偏序来处理带修改的情况。加点正权值，删点负权值即可。我们维护每个时刻相比前一个时刻逆序对的变化量，再在时间序列上做前缀和即可得到答案。

值得注意的是逆序对计算贡献的细节。时间作为第一维，下标作为第二维，值作为第三维，对于一个点，下标小于其下标且值大于其值的点，和下标大于其下标且值小于其值的点均要计入答案，所以双指针需要扫两遍。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

int n, m, cnt;
int t[N], ans[N], p[N], pos[N];
struct {
    int t, p, v, o;
} q[N];

void add(int x, int v) {
    while (x <= n) {
        t[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q[j + 1].p < q[i].p) {
            j++;
            add(q[j].v, q[j].o);
        }
        ans[q[i].t] += q[i].o * (query(n) - query(q[i].v));
    }
    for (int i = l; i <= j; ++i) {
        add(q[i].v, -q[i].o);
    }
    j = mid + 1;
    for (int i = r; i > mid; --i) {
        while (j - 1 >= l && q[j - 1].p > q[i].p) {
            j--;
            add(q[j].v, q[j].o);
        }
        ans[q[i].t] += q[i].o * (query(q[i].v - 1));
    }
    for (int i = mid; i >= j; --i) {
        add(q[i].v, -q[i].o);
    }
    sort(q + l, q + r + 1, [&](auto x, auto y) {
        return x.p < y.p;
    });
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        pos[p[i]] = i;
        ++cnt;
        q[cnt] = {0, i, p[i], 1};
    }
    for (int i = 1; i <= m; ++i) {
        int x;
        cin >> x;
        ++cnt;
        q[cnt] = {i, pos[x], x, -1};
    }
    cdq(1, cnt);
    for (int i = 1; i < m; ++i) {
        ans[i] += ans[i - 1];
    }
    for (int i = 0; i < m; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P2163 [SHOI2007] 园丁的烦恼

二维数点模板。k维数点本质上就是k维偏序，结合一下容斥原理即可。

k维数点/k维偏序的理想时间复杂度是$O(n\log^{k-1}{n})$，对于二维数点就是$O(n\log{n})$，分治内部如果直接使用库函数会导致复杂度不对，所以需要使用朴素的$O(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
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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 * 5 + 10;
constexpr int MOD = 998244353;

struct {
    int x, y, o, id;
} q[N], help[N];
int ans[N];
int n, m, cnt;

inline void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l - 1;
    for (int i = mid + 1, tree = 0; i <= r; ++i) {
        while (j + 1 <= mid && q[j + 1].y <= q[i].y) {
            j++;
            if (!q[j].id) tree++;
        }
        if (q[i].id) ans[q[i].id] += q[i].o * tree;
    }
    int p1 = l, p2 = mid + 1, i = l;
    while (p1 <= mid && p2 <= r) {
        help[i++] = q[p1].y <= q[p2].y ? q[p1++] : q[p2++];
    }
    while (p1 <= mid) {
        help[i++] = q[p1++];
    }
    while (p2 <= r) {
        help[i++] = q[p2++];
    }
    for (int i = l; i <= r; ++i) q[i] = help[i];
}

void solve() {
    int n, m;
    read(n, m);
    for (int i = 0; i < n; ++i) {
        int x, y;
        read(x, y);
        q[++cnt] = {x, y, 0, 0};
    }
    for (int i = 1; i <= m; ++i) {
        int a, b, c, d;
        read(a, b, c, d);
        q[++cnt] = {c, d, 1, i};
        q[++cnt] = {a - 1, b - 1, 1, i};
        q[++cnt] = {c, b - 1, -1, i};
        q[++cnt] = {a - 1, d, -1, i};
    }
    sort(q + 1, q + 1 + cnt, [&](auto x, auto y) {
        if (x.x != y.x) return x.x < y.x;
        return x.id < y.id;
    });
    cdq(1, cnt);
    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P3755 [CQOI2017] 老C的任务

二维数点的权值从1变成a，其他没有任何区别。美美双倍经验。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e6 * 3 + 10;
constexpr int MOD = 998244353;

struct {
    int x, y, v, id;
} q[N], help[N];
int ans[N];
int n, m, cnt;

inline void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l - 1;
    for (int i = mid + 1, tree = 0; i <= r; ++i) {
        while (j + 1 <= mid && q[j + 1].y <= q[i].y) {
            j++;
            if (!q[j].id) tree += q[j].v;
        }
        if (q[i].id) ans[q[i].id] += q[i].v * tree;
    }
    int p1 = l, p2 = mid + 1, i = l;
    while (p1 <= mid && p2 <= r) {
        help[i++] = q[p1].y <= q[p2].y ? q[p1++] : q[p2++];
    }
    while (p1 <= mid) {
        help[i++] = q[p1++];
    }
    while (p2 <= r) {
        help[i++] = q[p2++];
    }
    for (int i = l; i <= r; ++i) q[i] = help[i];
}

void solve() {
    int n, m;
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        int x, y, p;
        read(x, y, p);
        q[++cnt] = {x, y, p, 0};
    }
    for (int i = 1; i <= m; ++i) {
        int a, b, c, d;
        read(a, b, c, d);
        q[++cnt] = {c, d, 1, i};
        q[++cnt] = {a - 1, b - 1, 1, i};
        q[++cnt] = {c, b - 1, -1, i};
        q[++cnt] = {a - 1, d, -1, i};
    }
    sort(q + 1, q + 1 + cnt, [&](auto x, auto y) {
        if (x.x != y.x) return x.x < y.x;
        return x.id < y.id;
    });
    cdq(1, cnt);
    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4390 [BalkanOI 2007] Mokia 摩基亚

二维数点的基础上带单点修改。一样的套路，加入时间序列变成三维数点。

需要记得处理树状数组下标不为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
108
109
110
111
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e6 + 10;
constexpr int MOD = 998244353;

struct node {
    int x, y, t, v, id;
} q[N * 5];
int t[N], ans[N];
int w, cnt;

void add(int x, int v) {
    while (x <= w) {
        t[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q[j + 1].x <= q[i].x) {
            j++;
            if (!q[j].id) add(q[j].y, q[j].v);
        }
        if (q[i].id) ans[q[i].id] += q[i].v * query(q[i].y);
    }
    for (int i = l; i <= j; ++i) {
        if (!q[i].id) add(q[i].y, -q[i].v);
    }
    sort(q + l, q + r + 1, [&](auto x, auto y) {
        return x.x < y.x;
    });
}

void solve() {
    int op;
    cin >> op >> w;
    w++;
    int t = 0, m = 0;
    while (1) {
        cin >> op;
        int a, b, c, d;
        ++t;
        if (op == 1) {
            cin >> a >> b >> c;
            a++, b++;
            q[++cnt] = {a, b, t, c};
        } else if (op == 2) {
            cin >> a >> b >> c >> d; 
            a++, b++, c++, d++;
            ++m;
            q[++cnt] = {c, d, t, 1, m};
            q[++cnt] = {a - 1, b - 1, t, 1, m};
            q[++cnt] = {c, b - 1, t, -1, m};
            q[++cnt] = {a - 1, d, t, -1, m};
        } else {
            break;
        }
    }
    sort(q + 1, q + cnt + 1, [&](auto x, auto y) {
        if (x.t != y.t) return x.t < y.t;
        return x.x < y.x;
    });
    cdq(1, cnt);
    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4169 [Violet] 天使玩偶/SJY摆棋子

很有思维的一道题。询问的东西带绝对值，我们很不喜欢。考虑怎么去掉绝对值。

如果我们能保证询问点的横纵坐标都不小于实际点的横纵坐标，也就是实际点都在询问点的左下角，那么就能简单的去掉绝对值符号。

假设能做到这一点，我们使用树状数组维护前缀最大值，时间作为第一维排序，分治内部x作为第二维，y作为第三维放到树状数组上，用这个点的x+y之和去尝试更新最大值。那么询问点的答案就是这个点的x+y减去y坐标前缀在树状数组中记录的所有实际点的x+y最大值。

然而实际不能保证所有实际点都在询问点左下角。最妙的来了。我们把所有点在四个象限各变换一次，每个象限都询问一次，这样所有点在四次里至少有一次处于询问点的左下角，四次取最值即可。

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>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e6 + 10;
constexpr int MOD = 998244353;

struct {
    int x, y, id;
} q[N], qq[N];
int t[N], ans[N], limit;
int n, m, cnt;

void modify(int x, int v) {
    while (x <= limit) {
        t[x] = max(t[x], v);
        x += x & -x;
    }
}

int query(int x) {
    int res = -inf;
    while (x) {
        res = max(res, t[x]);
        x -= x & -x;
    }
    return res;
}

void clear(int x) {
    while (x <= limit) {
        t[x] = -inf;
        x += x & -x;
    }
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q[j + 1].x <= q[i].x) {
            j++;
            if (!q[j].id) modify(q[j].y, q[j].x + q[j].y);
        }
        if (q[i].id) {
            chkmin(ans[q[i].id], q[i].x + q[i].y - query(q[i].y));
        }
    }
    for (int i = l; i <= j; ++i) {
        if (!q[i].id) clear(q[i].y);
    }
    sort(q + l, q + r + 1, [&](auto x, auto y) {
        return x.x < y.x;
    });
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        x++;
        y++;
        qq[++cnt] = {x, y, 0};
        limit = max({limit, x, y});
    }
    int j = 0;
    for (int i = 1; i <= m; ++i) {
        int t, x, y;
        cin >> t >> x >> y;
        x++;
        y++;
        qq[++cnt] = {x, y, (t == 1 ? 0 : ++j)};
        limit = max({limit, x, y});
    }
    limit++;
    for (int i = 1; i <= j; ++i) ans[i] = inf;
    for (int i = 1; i <= limit; ++i) t[i] = -inf;
    for (int i = 1; i <= cnt; ++i) {
        q[i] = qq[i];
    }
    cdq(1, cnt);
    for (int i = 1; i <= cnt; ++i) {
        q[i] = qq[i];
        q[i].x = limit - q[i].x;
    }
    cdq(1, cnt);
    for (int i = 1; i <= cnt; ++i) {
        q[i] = qq[i];
        q[i].y = limit - q[i].y;
    }
    cdq(1, cnt);
    for (int i = 1; i <= cnt; ++i) {
        q[i] = qq[i];
        q[i].x = limit - q[i].x;
        q[i].y = limit - q[i].y;
    }
    cdq(1, cnt);
    for (int i = 1; i <= j; ++i) {
        cout << ans[i] << "\n";
    }

}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5094 [USACO04OPEN] MooFest G 加强版

两点之间贡献为声音较大值乘二者距离，问所有点对的贡献。

把所有点按照声音升序排序，分治的时候就能保证右边的声音一定是较大值。双指针，左边指针指向最大的坐标小于等于右边指针指向点的坐标的点，再维护两个变量lsum和rsum记录左边指针分隔的两部分的坐标和，分两部分即可求出坐标的贡献，也就是所有距离之和。

这题也可以用普通的BIT，两颗BIT分别记录数量和坐标和，简简单单也随便做。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct {
    int v, x;
} q[N], help[N];
int n;

int cdq(int l, int r) {
    if (l == r) return 0;
    int mid = l + r >> 1;
    int res = cdq(l, mid) + cdq(mid + 1, r);
    int lsum = 0, rsum = 0;
    for (int i = l; i <= mid; ++i) rsum += q[i].x;
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q[j + 1].x <= q[i].x) {
            j++;
            rsum -= q[j].x;
            lsum += q[j].x;
        }
        res += ((j - l + 1) * q[i].x - lsum) * q[i].v;
        res += (rsum - (mid - j) * q[i].x) * q[i].v;
    }
    int p1 = l, p2 = mid + 1, i = l;
    while (p1 <= mid && p2 <= r) {
        help[i++] = q[p1].x < q[p2].x ? q[p1++] : q[p2++];
    }
    while (p1 <= mid) {
        help[i++] = q[p1++];
    }
    while (p2 <= r) {
        help[i++] = q[p2++];
    }
    for (int i = l; i <= r; ++i) q[i] = help[i];
    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i].v >> q[i].x;
    }
    sort(q + 1, q + n + 1, [&](auto x, auto y) {
        return x.v < y.v;
    });
    cout << cdq(1, n) << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

CF1045G AI robots

机器人排成一排，有位置x，视野半径r，智商q参数，两个机器人能交流当且仅当二者均在对方视野中，且智商差值不大于定值k。问能相互交流的机器人对数量。

把所有机器人按照视野大小降序排序，这样右边如果能看到左边，那左边一定能看到右边，把互相看见的条件转为一方可看见。分治内部按智商维护一个滑动窗口，窗口内的机器人在树状数组中对应位置修改权值从而进行统计。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

struct {
    int x, y, q, l, r;
} q[N];
int a[N], t[N];
int n, k;

void add(int x, int v) {
    while (x <= n) {
        t[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

int query(int l, int r) {
    return query(r) - query(l - 1);
}

int cdq(int l, int r) {
    if (l == r) return 0;
    int mid = l + r >> 1;
    int res = cdq(l, mid) + cdq(mid + 1, r);
    int winl = l, winr = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (winl <= mid && q[winl].q < q[i].q - k) {
            add(q[winl].x, -1);
            winl++;
        }
        while (winr + 1 <= mid && q[winr + 1].q <= q[i].q + k) {
            winr++;
            add(q[winr].x, 1);
        }
        res += query(q[i].l, q[i].r);
    }
    for (int i = winl; i <= winr; ++i) {
        add(q[i].x, -1);
    }
    sort(q + l, q + r + 1, [&](auto x, auto y) {
        return x.q < y.q;
    });
    return res;
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i].x >> q[i].y >> q[i].q;
        a[i] = q[i].x;
    }
    sort(a + 1, a + 1 + n);
    int m = unique(a + 1, a + 1 + n) - a - 1;
    for (int i = 1; i <= n; ++i) {
        q[i].l = lower_bound(a + 1, a + m + 1, q[i].x - q[i].y) - a;
        q[i].r = upper_bound(a + 1, a + m + 1, q[i].x + q[i].y) - a - 1;
        q[i].x = lower_bound(a + 1, a + m + 1, q[i].x) - a;
    }
    sort(q + 1, q + 1 + n, [&](auto x, auto y) {
        return x.y > y.y;
    });
    cout << cdq(1, n) << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4093 [HEOI2016/TJOI2016] 序列

最多修改一次，问在任何修改情况下都保持不下降的子序列的最长长度。

分析题意，实质上是同时满足三个条件的转移：$dp[i] = \max(dp[j]) + 1, j \in \{j \mid j < i \land rv[j] \le v[i] \land v[j] \le lv[i]\}$。满足三个条件，本质上就是三维偏序，可以使用CDQ分治来优化DP转移过程。

此处需要注意CDQ分治优化DP和处理其他信息的区别：由于DP转移是带有方向性的，我们必须保证做完左组全部的转移后再处理右组，否则会导致错误。这就要求我们在CDQ分治时必须使用左中右的中序分治，即做完左组内部转移，再做左组向右组的转移，最后做右组内部转移。而其他信息，例如普通偏序问题，贡献的先后是没有区别的，所以使用左右中的后序和左中右的中序都可以。

如果必须使用左中右分治，实际排序就要显式排序两次，而不能像左右中那样最后整体排一次。

不过本题左右组排序指标不同，其实不会产生疑问，但在两组排序指标相同时，会产生写法上的一些问题，此处特地指出。

具体维护过程没有特别之处，树状数组的每个位置维护相应的DP值即可，类似其他数据结构优化DP。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

struct {
    int v, lv, rv, i;
} q[N], q1[N], q2[N];
int dp[N], t[N];
int n, m;

void modify(int x, int v) {
    while (x <= n) {
        chkmax(t[x], v);
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        chkmax(res, t[x]);
        x -= x & -x;
    }
    return res;
}

void clear(int x) {
    while (x <= n) {
        t[x] = 0;
        x += x & -x;
    }
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    for (int i = l; i <= mid; ++i) q1[i] = q[i];
    for (int i = mid + 1; i <= r; ++i) q2[i] = q[i];
    sort(q1 + l, q1 + mid + 1, [&](auto x, auto y) { return x.rv < y.rv; });
    sort(q2 + mid + 1, q2 + r + 1, [&](auto x, auto y) { return x.v < y.v; });
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q1[j + 1].rv <= q2[i].v) {
            j++;
            modify(q1[j].v, dp[q1[j].i]);
        }
        chkmax(dp[q2[i].i], query(q2[i].lv) + 1);
    }
    for (int i = l; i <= j; ++i) {
        clear(q1[i].v);
    }
    cdq(mid + 1, r);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        auto& [v, lv, rv, id] = q[i];
        cin >> v;
        lv = rv = v;
        id = i;
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        chkmin(q[x].lv, y);
        chkmax(q[x].rv, y);
    }
    for (int i = 1; i <= n; ++i) dp[i] = 1;
    cdq(1, n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        chkmax(ans, dp[i]);
    }
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

不写不知道，一写收获本题最优解。～ (∠・ω< )⌒★

P2487 [SDOI2011] 拦截导弹

给定序列，任意选一个三维偏序最长不上升子序列，计算其长度，以及每个元素被选择的概率。

我们计算最长子序列的长度和方案数，再计算每个元素在最长子序列的方案数即可。

定义四个信息：$len1[i]$ 表示以下标 $i$ 结尾的最长不上升子序列长度，$cnt1[i]$ 表示以下标 $i$ 结尾的最长不上升子序列数量；$len2[i]$ 表示以下标 $i$ 开头的最长不上升子序列长度，$cnt2[i]$ 表示以下标 $i$ 开头的最长不上升子序列数量。先看前两个信息，我们还是使用树状数组维护前缀最大信息，只不过此时同时维护前缀最大值和方案数。和上一道题的方法类似，很好进行转移。后两个信息是以 $i$ 开头的，怎么做？把整个序列翻转，等价于计算以下标 $i$ 结尾的最长不下降子序列长度和数量。

拿到四个信息后，$len1[i]$ 最大值就是答案，再遍历 $cnt1[i]$ 拿到所有方案数。最后遍历每个元素，如果 $len1[i] + len2[i] - 1 < maxlen$ 则该元素一定不在最长子序列中，否则方案数就是 $cnt1[i] \times cnt2[i]$，计算概率即可。

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 5e4 + 10;
constexpr int MOD = 998244353;

struct {
    int h, v, i;
} q[N], q2[N];
int t[N], a[N];
double sum[N];
int len1[N], len2[N];
double cnt1[N], cnt2[N];
int n, m;

void modify(int i, int v, double cnt) {
    while (i <= m) {
        if (v > t[i]) {
            t[i] = v;
            sum[i] = cnt;
        } else if (v == t[i]) {
            sum[i] += cnt;
        }
        i += i & -i;
    }
}

tuple<int, double> query(int i) {
    int mx = 0;
    double cnt = 0;
    while (i) {
        if (t[i] > mx) {
            mx = t[i];
            cnt = sum[i];
        } else if (t[i] == mx) {
            cnt += sum[i];
        }
        i -= i & -i;
    }
    return {mx, cnt};
}

void clear(int i) {
    while (i <= m) {
        t[i] = 0;
        sum[i] = 0;
        i += i & -i;
    }
}

void cdq1(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq1(l, mid);
    for (int i = l; i <= r; ++i) q2[i] = q[i];
    sort(q2 + l, q2 + mid + 1, [&](auto x, auto y) { return x.h > y.h; });
    sort(q2 + mid + 1, q2 + r + 1, [&](auto x, auto y) { return x.h > y.h; });
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q2[j + 1].h >= q2[i].h) {
            j++;
            modify(m - q2[j].v, len1[q2[j].i], cnt1[q2[j].i]);
        }
        auto [mx, cnt] = query(m - q2[i].v);
        if (mx + 1 > len1[q2[i].i]) {
            len1[q2[i].i] = mx + 1;
            cnt1[q2[i].i] = cnt;
        } else if (mx + 1 == len1[q2[i].i]) {
            cnt1[q2[i].i] += cnt;
        }
    }
    for (int i = l; i <= j; ++i) {
        clear(m - q2[i].v);
    }
    cdq1(mid + 1, r);
}

void cdq2(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq2(l, mid);
    for (int i = l; i <= r; ++i) q2[i] = q[i];
    sort(q2 + l, q2 + mid + 1, [&](auto x, auto y) { return x.h < y.h; });
    sort(q2 + mid + 1, q2 + r + 1, [&](auto x, auto y) { return x.h < y.h; });
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q2[j + 1].h <= q2[i].h) {
            j++;
            modify(q2[j].v, len2[q2[j].i], cnt2[q2[j].i]);
        }
        auto [mx, cnt] = query(q2[i].v);
        if (mx + 1 > len2[q2[i].i]) {
            len2[q2[i].i] = mx + 1;
            cnt2[q2[i].i] = cnt;
        } else if (mx + 1 == len2[q2[i].i]) {
            cnt2[q2[i].i] += cnt;
        }
    }
    for (int i = l; i <= j; ++i) {
        clear(q2[i].v);
    }
    cdq2(mid + 1, r);
}

void compute() {
    for (int i = 1; i <= n; ++i) {
        len1[i] = cnt1[i] = len2[i] = cnt2[i] = 1;
    }
    cdq1(1, n);
    for (int i = 1; i < n - i + 1; ++i) {
        swap(q[i], q[n - i + 1]);
    }
    for (int i = 1; i <= n; ++i) {
        q[i].i = i;
    }
    cdq2(1, n);
    for (int i = 1; i < n - i + 1; ++i) {
        swap(len2[i], len2[n - i + 1]);
        swap(cnt2[i], cnt2[n - i + 1]);
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        auto& [h, v, id] = q[i];
        cin >> h >> v;
        id = i;
        a[i] = v;
    }
    sort(a + 1, a + n + 1);
    m = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; ++i) {
        q[i].v = lower_bound(a + 1, a + m + 1, q[i].v) - a;
    }
    m++;
    compute();
    int len = 0;
    double cnt = 0;
    for (int i = 1; i <= n; ++i) len = max(len, len1[i]);
    for (int i = 1; i <= n; ++i) {
        if (len1[i] == len) cnt += cnt1[i];
    }
    cout << len << "\n";
    for (int i = 1; i <= n; ++i) {
        if (len1[i] + len2[i] - 1 < len) cout << "0 ";
        else cout << fixed << setprecision(5) << (cnt1[i] * cnt2[i] / cnt) << " ";
    }
    cout << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5621 [DBOI2019] 德丽莎世界第一可爱

四维偏序+子序列DP。

他来了他来了，心心念念的CDQ套CDQ他来了！

普通的CDQ分治只能处理三维偏序，我们注意到做一次CDQ本质上就是降一维，容易想到CDQ分治里再套一层CDQ分治，这样就可以转成三维偏序做了。

定义两个函数$CDQ1(l,r)$和$CDQ2(l,r)$，$CDQ1(l,r)$是外层分治，内部调用$CDQ2(l,r)$。最外层先按第一维排序，$CDQ1(l,r)$内部按照第二维排序，同时记录每个点来自第一维排序时的左组还是右组。排好序后调用$CDQ2(l,r)$，内部继续分成左右两组，保证其按照第三维有序。双指针来维护，此时左组整体在第二维上小于右组，但第一维的信息乱了，需要借助刚刚的原左右组标记。左右组的贡献过程实际上只有现左组中来自原左组的点可以给现右组中来自原右组的点贡献。这样思考：如果原右组的点跑到了原左组之前，说明其第二维或者第三维不满足偏序关系，实际上无法造成贡献，所以这样做是没问题的。第四维继续使用树状数组统计，每个点记录其对应的dp值，每次查询前缀最大值来进行转移。

一些细节：内部分治后还需要处理右组的贡献，所以点顺序不能乱。为防止排序打乱原顺序，拷贝一份，在新数组上给第二第三维排序即可。

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

struct {
    int a, b, c, d, v, f, i;
} q[N], q1[N], q2[N];
int t[N], a[N], dp[N];
int n, s;

void modify(int x, int v) {
    while (x <= s) {
        chkmax(t[x], v);
        x += x & -x;
    }
}

int query(int x) {
    int res = -inf;
    while (x) {
        chkmax(res, t[x]);
        x -= x & -x;
    }
    return res;
}

void clear(int x) {
    while (x <= s) {
        t[x] = -inf;
        x += x & -x;
    }
}

void merge(int l, int r) {
    int mid = l + r >> 1;
    for (int i = l; i <= r; ++i) {
        q2[i] = q1[i];
    }
    stable_sort(q2 + l, q2 + mid + 1, [&](auto x, auto y) {
        return x.c < y.c;
    });
    stable_sort(q2 + mid + 1, q2 + r + 1, [&](auto x, auto y) {
        return x.c < y.c;
    });
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q2[j + 1].c <= q2[i].c) {
            j++;
            if (q2[j].f == 1) {
                modify(q2[j].d, dp[q2[j].i]);
            }
        }
        if (q2[i].f == 0) {
            chkmax(dp[q2[i].i], query(q2[i].d) + q2[i].v);
        }
    }
    for (int i = l; i <= j; ++i) {
        if (q2[i].f) clear(q2[i].d);
    }
}

void cdq2(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq2(l, mid);
    merge(l, r);
    cdq2(mid + 1, r);
}

void cdq1(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq1(l, mid);
    for (int i = l; i <= r; ++i) {
        q1[i] = q[i];
        q1[i].f = i <= mid;
    }
    stable_sort(q1 + l, q1 + r + 1, [&](auto x, auto y) {
        return x.b < y.b;
    });
    cdq2(l, r);
    cdq1(mid + 1, r);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d >> q[i].v;
        a[i] = q[i].d;
    }
    sort(a + 1, a + n + 1);
    s = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; ++i) {
        q[i].d = lower_bound(a + 1, a + s + 1, q[i].d) - a;
    }
    stable_sort(q + 1, q + n + 1, [&](auto x, auto y) {
        if (x.a != y.a) return x.a < y.a;
        if (x.b != y.b) return x.b < y.b;
        if (x.c != y.c) return x.c < y.c;
        if (x.d != y.d) return x.d < y.d;
        return x.v > y.v;
    });
    int m = 1;
    for (int i = 2; i <= n; ++i) {
        if (q[i].a != q[m].a || q[i].b != q[m].b || q[i].c != q[m].c || q[i].d != q[m].d) {
            q[++m] = q[i];
        } else {
            if (q[i].v > 0) q[m].v += q[i].v;
        }
    }
    for (int i = 1; i <= m; ++i) q[i].i = i, dp[i] = q[i].v;
    memset(t, -inf, sizeof(t));
    cdq1(1, m);
    int ans = -inf;
    for (int i = 1; i <= m; ++i) ans = max(ans, dp[q[i].i]);
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

Bonus: CDQ套CDQ做三维偏序

来点真正能理解CDQ分治本质的东西吧。

我们最开始写的CDQ处理三维偏序，内部实际上使用了树状数组同时完成了两个维度信息的统计。后来使用CDQ套CDQ，内部再使用BIT来处理四维偏序。一个很自然的想法是，三维偏序能不能不使用树状数组，仅使用CDQ套CDQ来完成？答案是肯定的，具体而言内部的CDQ使用朴素的归并，在归并过程中统计信息。

缺点就是细节很多，而且常数比BIT大一倍，仅有学习价值。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct {
    int a, b, c, ans, cnt, id, f;
} q[N], q1[N], help[N];
int ans[N];
int n, k;

void cdq2(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq2(l, mid);
    cdq2(mid + 1, r);
    int p1 = l, p2 = mid + 1, i = l, cnt = 0;
    while (p1 <= mid && p2 <= r) {
        if (q1[p1].c <= q1[p2].c) {
            if (q1[p1].f) cnt += q1[p1].cnt;
            help[i++] = q1[p1++];
        } else {
            if (!q1[p2].f) q[q1[p2].id].ans += cnt;
            help[i++] = q1[p2++];
        }
    }
    while (p1 <= mid) {
        if (q1[p1].f) cnt += q1[p1].cnt;
        help[i++] = q1[p1++];
    }
    while (p2 <= r) {
        if (!q1[p2].f) q[q1[p2].id].ans += cnt;
        help[i++] = q1[p2++];
    }
    for (int i = l; i <= r; ++i) q1[i] = help[i];
}

void cdq1(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq1(l, mid);
    cdq1(mid + 1, r);
    int p1 = l, p2 = mid + 1, i = l;
    while (p1 <= mid && p2 <= r) {
        if (q[p1].b <= q[p2].b) {
            help[i] = q[p1++];
            help[i].f = 1;
        } else {
            help[i] = q[p2++];
            help[i].f = 0;
        }
        i++;
    }
    while (p1 <= mid) {
        help[i] = q[p1++];
        help[i].f = 1;
        i++;
    }
    while (p2 <= r) {
        help[i] = q[p2++];
        help[i].f = 0;
        i++;
    }
    for (int i = l; i <= r; ++i) q[i] = help[i], q1[i] = q[i], q1[i].id = i;
    cdq2(l, r);
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i].a >> q[i].b >> q[i].c;
    }
    sort(q + 1, q + n + 1, [&](auto x, auto y) {
        if (x.a != y.a) return x.a < y.a;
        if (x.b != y.b) return x.b < y.b;
        return x.c < y.c; 
    });
    int m = 0;
    for (int i = 1, cnt = 0; i <= n; ++i) {
        cnt++;
        if (q[i].a == q[i + 1].a && q[i].b == q[i + 1].b && q[i].c == q[i + 1].c) {
            continue;
        } else {
            q[++m] = q[i];
            q[m].cnt = cnt;
            cnt = 0;
        }
    }
    cdq1(1, m);
    for (int i = 1; i <= m; ++i) {
        ans[q[i].ans + q[i].cnt - 1] += q[i].cnt;
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P3769 [CH弱省胡策R2] TATT

问满足四维偏序的最长不下降子序列长度。

有了P5621，本题就是双倍经验。

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
134
135
136
137
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

struct {
    int a, b, c, d, f, i;
} q[N], q1[N], q2[N];
int t[N], a[N], dp[N];
int n, s;

void modify(int x, int v) {
    while (x <= s) {
        chkmax(t[x], v);
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        chkmax(res, t[x]);
        x -= x & -x;
    }
    return res;
}

void clear(int x) {
    while (x <= s) {
        t[x] = 0;
        x += x & -x;
    }
}

void merge(int l, int r) {
    int mid = l + r >> 1;
    for (int i = l; i <= r; ++i) {
        q2[i] = q1[i];
    }
    stable_sort(q2 + l, q2 + mid + 1, [&](auto x, auto y) {
        return x.c < y.c;
    });
    stable_sort(q2 + mid + 1, q2 + r + 1, [&](auto x, auto y) {
        return x.c < y.c;
    });
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q2[j + 1].c <= q2[i].c) {
            j++;
            if (q2[j].f == 1) {
                modify(q2[j].d, dp[q2[j].i]);
            }
        }
        if (q2[i].f == 0) {
            chkmax(dp[q2[i].i], query(q2[i].d) + 1);
        }
    }
    for (int i = l; i <= j; ++i) {
        if (q2[i].f) clear(q2[i].d);
    }
}

void cdq2(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq2(l, mid);
    merge(l, r);
    cdq2(mid + 1, r);
}

void cdq1(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq1(l, mid);
    for (int i = l; i <= r; ++i) {
        q1[i] = q[i];
        q1[i].f = i <= mid;
    }
    stable_sort(q1 + l, q1 + r + 1, [&](auto x, auto y) {
        return x.b < y.b;
    });
    cdq2(l, r);
    cdq1(mid + 1, r);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d;
        a[i] = q[i].d;
    }
    sort(a + 1, a + n + 1);
    s = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; ++i) {
        q[i].d = lower_bound(a + 1, a + s + 1, q[i].d) - a;
    }
    stable_sort(q + 1, q + n + 1, [&](auto x, auto y) {
        if (x.a != y.a) return x.a < y.a;
        if (x.b != y.b) return x.b < y.b;
        if (x.c != y.c) return x.c < y.c;
        return x.d < y.d;
    });
    for (int i = 1; i <= n; ++i) q[i].i = i, dp[i] = 1;
    cdq1(1, n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, dp[q[i].i]);
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4849 寻找宝藏

CDQ分治期末考试题。计算四维偏序不下降子序列的最大权值和及取到最大值的方案数。

CDQ套CDQ优化DP，树状数组维护同时维护前缀最大值和次数即可。

有了前几道题的基础，本题轻松拿下，恭喜，你已经相当熟悉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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

struct {
    int a, b, c, d, v, i, f;
} q[N], q1[N], q2[N];
int tree[N], treeSum[N];
int h[N];
int n, m;
int dp[N], cnt1[N];

void modify(int i, int v, int cnt) {
    while (i <= m) {
        if (v > tree[i]) {
            tree[i] = v;
            treeSum[i] = cnt;
        } else if (v == tree[i]) {
            treeSum[i] = (treeSum[i] + cnt) % MOD;
        }
        i += i & -i;
    }
}

tuple<int, int> query(int i) {
    int mx = 0, cnt = 0;
    while (i) {
        if (tree[i] > mx) {
            mx = tree[i];
            cnt = treeSum[i];
        } else if (tree[i] == mx) {
            cnt = (cnt + treeSum[i]) % MOD;
        }
        i -= i & -i;
    }
    return {mx, cnt};
}

void clear(int i) {
    while (i <= m) {
        tree[i] = 0;
        treeSum[i] = 0;
        i += i & -i;
    }
}

void cdq2(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq2(l, mid);
    for (int i = l; i <= r; ++i) q2[i] = q1[i];
    stable_sort(q2 + l, q2 + mid + 1, [&](auto x, auto y) { return x.c < y.c; });
    stable_sort(q2 + mid + 1, q2 + r + 1, [&](auto x, auto y) { return x.c < y.c; });
    int j = l - 1;
    for (int i = mid + 1; i <= r; ++i) {
        while (j + 1 <= mid && q2[j + 1].c <= q2[i].c) {
            j++;
            if (q2[j].f) modify(q2[j].d, dp[q2[j].i], cnt1[q2[j].i]);
        }
        if (q2[i].f) continue;
        auto [mx, cnt] = query(q2[i].d);
        if (mx + q2[i].v > dp[q2[i].i]) {
            dp[q2[i].i] = mx + q2[i].v;
            cnt1[q2[i].i] = cnt;
        } else if (mx + q2[i].v == dp[q2[i].i]) {
            cnt1[q2[i].i] = (cnt1[q2[i].i] + cnt) % MOD;
        }
    }
    for (int i = l; i <= j; ++i) {
        if (q2[i].f) clear(q2[i].d);
    }
    cdq2(mid + 1, r);
}

void cdq1(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq1(l, mid);
    for (int i = l; i <= r; ++i) {
        q1[i] = q[i];
        q1[i].f = i <= mid;
    }
    stable_sort(q1 + l, q1 + r + 1, [&](auto x, auto y) { return x.b < y.b; });
    cdq2(l, r);
    cdq1(mid + 1, r);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d >> q[i].v;
        h[i] = q[i].d;
    }
    sort(h + 1, h + n + 1);
    m = unique(h + 1, h + n + 1) - h - 1;
    for (int i = 1; i <= n; ++i) q[i].d = lower_bound(h + 1, h + m + 1, q[i].d) - h;
    sort(q + 1, q + n + 1, [&](auto x, auto y) {
        if (x.a != y.a) return x.a < y.a;
        if (x.b != y.b) return x.b < y.b;
        if (x.c != y.c) return x.c < y.c;
        return x.d < y.d;
    });
    
    // 去不去重均可
    int t = 1;
    for (int i = 2; i <= n; ++i) {
        if (q[i].a == q[t].a && q[i].b == q[t].b && q[i].c == q[t].c && q[i].d == q[t].d) {
            q[t].v += q[i].v;
        } else {
            q[++t] = q[i];
        }
    }
    n = t;
    // end
    for (int i = 1; i <= n; ++i) q[i].i = i, dp[i] = q[i].v, cnt1[i] = 1;

    cdq1(1, n);
    int mx = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) mx = max(mx, dp[i]);
    for (int i = 1; i <= n; ++i) if (dp[i] == mx) cnt = (cnt + cnt1[i]) % MOD;
    cout << mx << "\n" << cnt << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

结语

和其他离线算法一样，在强制在线越来越少的当下环境中，CDQ分治作为一种离线算法显得愈发美妙。其处理点对贡献的强大之处，使得CDQ分治成为了许多选手的必备武器。它能够有效的提升选手思维，非常值得一学。