跳转至

cdq 分治

技巧

cdq 分治的核心功能是：对一个没有单调性的序列，统计单调性产生的贡献。或：通过分治创造出单调性。

例如，三维数点中，我们将所有点按 \(a_i\) 排序，\(b_i\) 就没有单调性了，cdq 分治能将 \(b_i\) “转换”为具有单调性的子问题，从而通过树状数组求解。

cdq 分治处理三维偏序

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

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

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

其中 \(1\le n\le 10^5,\ 1\le a_i,b_i,c_i\le 2\times 10^5\)

我们先将所有操作按照 \(c_i\) 升序排序，使得后面的修改操作不可能贡献到前面的查询操作，由此去掉了 \(c_i\) 维度。

分治过程

考虑分治，设我们现在要处理的操作 \(op\) 都满足 \(a_i\in[l,r]\)。

1
void cdq(int l, int r, vector<Point> &op);

取中点 \(mid=\frac{l+r}{2}\)，将所有 \(op\) 分成两部分：\(a_i\in[l,mid]\) 和 \(a_i\in[mid+1,r]\)。记左区间为 \(lc\)，右区间为 \(rc\)。在本层分治中，我们只统计 \(lc\) 的 modify 对 \(rc\) 中 query 的贡献。而两区间内部的贡献则交由下一层递归处理。

cdq01

如图，我们只处理横跨两区间的贡献。

如何处理横跨两区间的贡献呢？我们首先筛选出 \(lc\) 中的 modify 和 \(rc\) 的 query；然后按照下标顺序依次处理（即按照 \(c_i\) 的顺序）；用树状数组维护 \(b_i\) 即可。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
int mid = (l + r) >> 1;
for(int i = 0; i < op.size(); i++) {
    // 只处理左区间的修改对右区间查询的贡献
    // 按顺序才能保证 c[i] 单调不降，所以可以不考虑 c[i] 的限制
    if(op[i].a <= mid && op[i].op == 1) BIT::modify(op[i].b, 1);
    if(op[i].a > mid && op[i].op == 0) ans[op[i].num] += BIT::query(op[i].b);
}
// 撤销修改
for(int i = 0; i < op.size(); i++) {
    if(op[i].a <= mid && op[i].op == 1) BIT::modify(op[i].b, -1);
}
// 将区间按 a 分成两部分
vector<Point> lop, rop;
for(int i = 0; i < op.size(); i++) {
    if(op[i].a <= mid) lop.push_back(op[i]);
    else rop.push_back(op[i]);
}
// 递归统计两区间内部的贡献
cdq(l, mid, lop);
cdq(mid + 1, r, rop);

终止条件

当区间大小为 \(1\) 时，即 \(l=r\) 时，所有操作的 \(a_i\) 相等。此时问题退化为关于 \(b_i\) 和 \(c_i\) 的简单二维数点，直接用树状数组统计逆序对即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
if(l == r) {
    // 就是二维数点
    for(int i = 0; i < op.size(); i++) {
        if(op[i].op == 1) BIT::modify(op[i].b, 1);
        if(op[i].op == 0) ans[op[i].num] += BIT::query(op[i].b);
    }
    // 一定要撤销 BIT 上的修改
    for(int i = 0; i < op.size(); i++) {
        if(op[i].op == 1) BIT::modify(op[i].b, -1);
    }
    return;
}

时间复杂度分析

  • 对于 op 中的每一个操作，都会在分治时产生一条从根走到叶子的路径，时间复杂度 \(O(\log V)\)；
  • 同时每一个操作都会在每次分治时处调用数据结构，在路径上的每一个节点处产生 \(O(\log V)\) 的时间复杂度，一次操作就会产生 \(O(\log^2 V)\) 的时间复杂度；
  • 总共有 \(n\) 个操作，因此总时间复杂度为 \(O(n\log^2 V)\)。

值域范围内的 cdq 必须剪枝

如果调用 cdq 时，传入的区间是整个值域，如果不剪枝，时间复杂度将会达到 \(O(V)\)。这是因为，即使 op 为空，仍然会继续递归，这会导致许多没被有效路径覆盖到的节点也进行了递归。

因此需要在 cdq 函数内部的开头判断 op.empty()，才能保证时间复杂度的正确性。

本文中的 cdq 套 cdq 以及整体二分都需要剪枝。

核心代码 
1
2
3
4
5
6
7
struct Point {
    int op, a, b, c, num;
    inline bool operator<(const Point& other) const {
        if(c != other.c) return c < other.c;
        return op > other.op;
    }
};

 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
void cdq(int l, int r, vector<Point> &op) {
    if(l == r) {
        for(int i = 0; i < op.size(); i++) {
            if(op[i].op == 1) BIT::modify(op[i].b, 1);
            if(op[i].op == 0) ans[op[i].num] += BIT::query(op[i].b);
        }
        for(int i = 0; i < op.size(); i++) {
            if(op[i].op == 1) BIT::modify(op[i].b, -1);
        }
        return;
    }
    int mid = (l + r) >> 1;
    for(int i = 0; i < op.size(); i++) {
        if(op[i].a <= mid && op[i].op == 1) BIT::modify(op[i].b, 1);
        if(op[i].a > mid && op[i].op == 0) ans[op[i].num] += BIT::query(op[i].b);
    }
    for(int i = 0; i < op.size(); i++) {
        if(op[i].a <= mid && op[i].op == 1) BIT::modify(op[i].b, -1);
    }
    vector<Point> lop, rop;
    for(int i = 0; i < op.size(); i++) {
        if(op[i].a <= mid) lop.push_back(op[i]);
        else rop.push_back(op[i]);
    }
    cdq(l, mid, lop);
    cdq(mid + 1, r, rop);
}
AC代码 
 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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1E5 + 10;
const int M = 2E5 + 10;

struct Point {
    int op, a, b, c, num;
    inline bool operator<(const Point& other) const {
        if(c != other.c) return c < other.c;
        return op > other.op;
    }
};

int n, k;
int ans[N], cnt[N];

namespace BIT {
    int sum[M];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, int v) {
        for(int i = p; i <= k; i += lowbit(i)) {
            sum[i] += v;
        }
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += sum[i];
        }
        return res;
    }
}

void cdq(int l, int r, vector<Point> &op) {
    if(l == r) {
        for(int i = 0; i < op.size(); i++) {
            if(op[i].op == 1) BIT::modify(op[i].b, 1);
            if(op[i].op == 0) ans[op[i].num] += BIT::query(op[i].b);
        }
        for(int i = 0; i < op.size(); i++) {
            if(op[i].op == 1) BIT::modify(op[i].b, -1);
        }
        return;
    }
    int mid = (l + r) >> 1;
    for(int i = 0; i < op.size(); i++) {
        if(op[i].a <= mid && op[i].op == 1) BIT::modify(op[i].b, 1);
        if(op[i].a > mid && op[i].op == 0) ans[op[i].num] += BIT::query(op[i].b);
    }
    for(int i = 0; i < op.size(); i++) {
        if(op[i].a <= mid && op[i].op == 1) BIT::modify(op[i].b, -1);
    }
    vector<Point> lop, rop;
    for(int i = 0; i < op.size(); i++) {
        if(op[i].a <= mid) lop.push_back(op[i]);
        else rop.push_back(op[i]);
    }
    cdq(l, mid, lop);
    cdq(mid + 1, r, rop);
}

vector<Point> op;

int main() {

    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        op.push_back({0, a, b, c, i});
        op.push_back({1, a, b, c, i});
    }

    sort(op.begin(), op.end());

    cdq(1, k, op);

    for(int i = 1; i <= n; i++) {
        cnt[ans[i] - 1]++;
    }
    for(int i = 0; i < n; i++) {
        cout << cnt[i] << '\n';
    }

    return 0;
}

cdq 优化 dp

P2487 [SDOI2011] 拦截导弹

有 \(n\) 发导弹按顺序依次发射，有一套拦截系统对它们进行拦截。每发导弹具有两个属性 \(a_i\) 和 \(b_i\)，要求拦截的导弹的 \(a_i\) 和 \(b_i\) 值均单调不升，并且拦截导弹的顺序必须按照导弹发射的顺序。

拦截系统总是选择拦截导弹数量最多的方案。若有多种方案，则任选一种。问每发导弹被拦截的概率是多少。

考虑 DP。设 \(dp_{i,1}\) 表示以第 \(i\) 发导弹为结尾，拦截导弹数量的最大值 \(val\) 和其方案数 \(cnt\)；\(dp_{i,2}\) 则表示以第 \(i\) 发导弹开始，拦截导弹数量的最大值 \(val\) 和其方案数 \(cnt\)。

很明显，拦截导弹数量的最大值就是 \(\max\{dp_{i,1}.val\}\) 或 \(\max\{dp_{i,2}.val\}\)，记为 \(ans\)，全局最优解的总方案数为 \(cnt\)。那么，每发导弹被拦截的概率就是

\[ \begin{cases} \frac{dp_{i,1}.cnt\times dp_{i,2}.cnt}{cnt},& dp_{i,1}.val+dp_{i,2}.val=ans\\ 0,&dp_{i,1}.val+dp_{i,2}.val<ans \end{cases} \]

考虑如何转移。朴素的转移方程式是

\[ f_{i,1}=\max_{j<i,\ a_j\le a_i,\ b_j\le b_i}\{f_{j,1}\}+1 \]

至于如何统计最优解的方案数 \(cnt\)，我们只需要在更新时判断一下，若 f[i].val == f[j].val，那么 f[i].cnt += f[j].cnt；否则如果 \(j\) 的 \(val\) 比 \(i\) 小，则不更新；否则直接 f[i].cnt = f[j].cnt。

此种转移的时间复杂度达到了 \(O(n^2)\)，考虑优化。

我们注意到，转移可以被理解为：同时处理 \(i\)，\(a_i\)，\(b_i\) 的三维约束。考虑 cdq 分治。

我们用 cdq 分治 \(a_i\) 维度，这样 \(a_i\) 维度上就“出现”了单调性。接下来，只需要使用树状数组对 \(b_i\) 维度处理即可。具体的，将所有操作按 \(a_i\) 分成两部分，先递归左区间处理其内部贡献，使得左区间的 \(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
void cdq_1(int l, int r, vector<int> &op) {
    // 处理边界条件
    if(l == r) {
        // 简单二维数点
        for(int i : op) {
            // 我的 dp 数组是一个结构体，同时记录最优解和方案数，max 函数也是自己写的，能合并两者的 cnt。
            f1[i] = max(f1[i], BIT::query(n - p[i].b + 1));
            // 这里要将 cnt 限制在 1 以上，是因为上一行可能会将 f[i].cnt 设为 0，但这样会导致一些问题，因此要加这个特判。
            f1[i].cnt = max(f1[i].cnt, 1.0);
            BIT::modify(n - p[i].b + 1, f1[i] + 1);
        }
        // BIT log 复杂度清空
        for(int i : op) {
            BIT::clear(n - p[i].b + 1);
        }
        return;
    }
    // 分割区间
    int mid = (l + r) >> 1;
    vector<int> lop, rop;
    for(int i : op) {
        if(p[i].a <= mid) lop.push_back(i);
        else rop.push_back(i);
    }
    // 处理左区间内部贡献
    cdq_1(mid + 1, r, rop);
    // 用树状数组统计左对右的贡献
    for(auto i : op) {
        if(p[i].a > mid) BIT::modify(n - p[i].b + 1, f1[i]);
        else f1[i] = max(f1[i], BIT::query(n - p[i].b + 1) + 1);
        f1[i].cnt = max(f1[i].cnt, 1.0);
    }
    for(auto i : op) {
        if(p[i].a > mid) BIT::clear(n - p[i].b + 1);
    }
    // 将右侧内部的贡献和左侧产生的贡献合并
    cdq_1(l, mid, lop);
}
AC代码 
  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<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<cstdio>
#define int long long
using namespace std;
const int N = 5E4 + 10;

struct myPair {
    int val; // 长度
    double cnt; // 方案数
    inline myPair(int _val = 0, double _cnt = 0) {
        val = _val;
        cnt = _cnt;
    }
    inline myPair operator+(int x) const {
        return {val + x, cnt};
    }
};

myPair max(const myPair& a, const myPair& b) {
    myPair res = {max(a.val, b.val), 0};
    if(res.val == a.val) res.cnt += a.cnt;
    if(res.val == b.val) res.cnt += b.cnt;
    return res;
}

struct Point {
    int a, b;
} p[N];

void lisanhua(int n) {
    int num[N], nn = 0;
    for(int i = 1; i <= n; i++) {
        num[++nn] = p[i].a;
    }
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        p[i].a = lower_bound(num + 1, num + 1 + nn, p[i].a) - num;
    }
    nn = 0;
    for(int i = 1; i <= n; i++) {
        num[++nn] = p[i].b;
    }
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        p[i].b = lower_bound(num + 1, num + 1 + nn, p[i].b) - num;
    }
}

int n;
myPair f1[N], f2[N];

namespace BIT {
    myPair tr[N];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, myPair v) {
        for(int i = p; i <= n; i += lowbit(i)) {
            tr[i] = max(tr[i], v);
        }
    }
    inline void clear(int p) {
        for(int i = p; i <= n; i += lowbit(i)) {
            tr[i].val = 0;
            tr[i].cnt = 0;
        }
    }
    inline myPair query(int p) {
        myPair res;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res = max(res, tr[i]);
        }
        return res;
    }
}

void cdq_1(int l, int r, vector<int> &op) {
    if(l == r) {
        for(int i : op) {
            f1[i] = max(f1[i], BIT::query(n - p[i].b + 1));
            f1[i].cnt = max(f1[i].cnt, 1.0);
            BIT::modify(n - p[i].b + 1, f1[i] + 1);
        }
        for(int i : op) {
            BIT::clear(n - p[i].b + 1);
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<int> lop, rop;
    for(int i : op) {
        if(p[i].a <= mid) lop.push_back(i);
        else rop.push_back(i);
    }
    cdq_1(mid + 1, r, rop);
    for(auto i : op) {
        if(p[i].a > mid) BIT::modify(n - p[i].b + 1, f1[i]);
        else f1[i] = max(f1[i], BIT::query(n - p[i].b + 1) + 1);
        f1[i].cnt = max(f1[i].cnt, 1.0);
    }
    for(auto i : op) {
        if(p[i].a > mid) BIT::clear(n - p[i].b + 1);
    }
    cdq_1(l, mid, lop);
}

void cdq_2(int l, int r, vector<int> &op) {
    if(l == r) {
        for(int i : op) {
            f2[i] = max(f2[i], BIT::query(p[i].b) + 1);
            f2[i].cnt = max(f2[i].cnt, 1.0);
            BIT::modify(p[i].b, f2[i]);
        }
        for(int i : op) {
            BIT::clear(p[i].b);
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<int> lop, rop;
    for(int i : op) {
        if(p[i].a <= mid) lop.push_back(i);
        else rop.push_back(i);
    }
    cdq_2(l, mid, lop);
    for(auto i : op) {
        if(p[i].a <= mid) BIT::modify(p[i].b, f2[i]);
        else f2[i] = max(f2[i], BIT::query(p[i].b) + 1);
        f2[i].cnt = max(f2[i].cnt, 1.0);
    }
    for(auto i : op) {
        if(p[i].a <= mid) BIT::clear(p[i].b);
    }
    cdq_2(mid + 1, r, rop);
}

vector<int> op;

signed main() {

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> p[i].a >> p[i].b;
    }

    lisanhua(n);

    for(int i = 1; i <= n; i++) {
        // BIT::tr[i].cnt = 1;
        f1[i].cnt = f2[i].cnt = 1;
    }

    for(int i = 1; i <= n; i++) {
        op.push_back(i);
    }

    cdq_1(1, n, op);

    reverse(op.begin(), op.end());
    cdq_2(1, n, op);

    myPair ans = {0, 0};
    for(int i = 1; i <= n; i++) {
        ans = max(ans, f1[i]);
    }
    cout << ans.val << endl;

    for(int i = 1; i <= n; i++) {
        if(f1[i].val + f2[i].val - 1 != ans.val) printf("%.6lf ", (double)0.0);
        else printf("%.6lf ", (double)f1[i].cnt * f2[i].cnt / ans.cnt);
    }
    cout << endl;

    return 0;
}

cdq 套 cdq

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

给定 \(n\) 个元素，每个元素有 \(5\) 个属性 \(a_i\)，\(b_i\)，\(c_i\)，\(d_i\)，\(e_i\)。你需要选出若干个元素，使得它们排序后满足 \(a_i\)，\(b_i\)，\(c_i\)，\(d_i\) 均单调不降。求 \(\sum{e_i}\) 的最大值。

这是一种类似最长上升子序列的问题，考虑 DP。我们设 \(dp_i\) 表示以第 \(i\) 个元素为结尾，\(\sum{e_i}\) 的最大值。容易写出转移方程：

\[ f_i=\max_{a_j\le a_i,\cdots, d_j\le d_i}\{f_j\}+e_i \]

时间复杂度 \(O(n^2)\)，需要优化。

不难发现，\(j\rightarrow i\) 的转移必须满足一个四维偏序关系。考虑使用 cdq 分治求解。

我们将所有元素按照 \(d_i\) 升序排序，只要在后续处理中不改变元素之间的相对位置，就可以不用考虑 \(d_i\) 的限制。

我们对 \(a_i\) 进行分治：

1
void cdq_1(int l, int r, vector<int> &op);

我们发现，计算区间 \(a_i\in[l,mid]\) 向区间 \(a_i\in[mid+1,r]\) 产生的贡献是一个三维偏序问题：

筛选出 \(a_j\in[l,mid]\) 的 \(f_j\) 和 \(a_i\in[mid+1,r]\) 的 \(f_i\)（这不是偏序关系，只是一个区间形式的约束）；并且在不改变序列下标顺序的情况下，还要满足 \(b\) 和 \(c\) 的偏序关系；然后从 \(j\) 转移到 \(i\)。

这正是一个在线二维数点问题。可以再套一个 cdq 来解决这个子问题。

因此，我们将 cdq 函数中 原本计算左区间向右区间贡献的代码 ，替换为另一 cdq 函数对 \(b_i\) 进行分治：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void cdq_1(int l, int r, vector<int> &op) {
    if(op.empty()) return;
    if(l == r) {
        cdq_2(1, n, op, l, l);
        return;
    }
    int mid = (l + r) >> 1;
    vector<int> lop, rop;
    for(int i = 0; i < op.size(); i++) {
        if(p[op[i]].a <= mid) lop.push_back(op[i]);
        else rop.push_back(op[i]);
    }
    // 1.统计左区间内部的所有贡献，并将左区间的 f[i] 更新到最优；
    // 2.将左区间贡献到右区间；
    // 3.在右区间合并左区间和自己本身的贡献；
    cdq_1(l, mid, lop);
    cdq_2(1, n, op, mid, mid + 1);
    cdq_1(mid + 1, r, rop);
}

考虑 cdq_2：

1
void cdq_2(int l, int r, vector<int> &op, int x, int y);

这段代码表示，传入的所有 \(op\) 都保证满足 \(b_i\in[l,r]\)，要求统计 \(a_i\le x\) 的元素对 \(a_i\ge y\) 的元素产生的贡献（不满足 \(a_i\) 条件的元素直接忽略。注意：这个约束不是偏序关系）。我们仍然使用 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
void cdq_2(int l, int r, vector<int> &op, int x, int y) {
    if(op.empty()) return;
    if(l == r) {
        // 简单二维数点 + a[i] 的限制
        for(int i = 0; i < op.size(); i++) {
            if(p[op[i]].a >= y) f[op[i]] = max(f[op[i]], BIT::query(p[op[i]].c) + p[op[i]].e);
            if(p[op[i]].a <= x) BIT::modify(p[op[i]].c, f[op[i]]);
        }
        for(int i = 0; i < op.size(); i++) {
            if(p[op[i]].a <= x) BIT::clear(p[op[i]].c);
        }
        return;
    }
    // 分裂区间
    int mid = (l + r) >> 1;
    vector<int> lop, rop;
    for(int i = 0; i < op.size(); i++) {
        if(p[op[i]].b <= mid) lop.push_back(op[i]);
        else rop.push_back(op[i]);
    }
    // 为什么必须把统计跨区间贡献的代码放在两个递归中间呢
    // 因为右区间可能会收到左区间产生的贡献，必须要先把左区间的所有贡献都统计完，通过中间的代码贡献到右区间，才能保证右区间的最优性。
    cdq_2(l, mid, lop, x, y);
    for(int i = 0; i < op.size(); i++) {
        // a[i] 的要求是 cdq_1 赋予的；
        // b[i] 的要求则是产生贡献的充分条件。
        if(p[op[i]].a <= x && p[op[i]].b <= mid) BIT::modify(p[op[i]].c, f[op[i]]);
        if(p[op[i]].a >= y && p[op[i]].b > mid) f[op[i]] = max(f[op[i]], BIT::query(p[op[i]].c) + p[op[i]].e);
    }
    for(int i = 0; i < op.size(); i++) {
        if(p[op[i]].a <= x && p[op[i]].b <= mid) BIT::clear(p[op[i]].c);
    }
    cdq_2(mid + 1, r, rop, x, y);
}

这样，我们通过两层 cdq，分别创造出两个维度的单调性。再按照 \(op\) 传入的顺序进行 dp 转移，再使用树状数组维护一个维度，就能求出答案。

数颜色

P1903 [国家集训队] 数颜色 / 维护队列

题意

你需要维护一个长度为 \(n\) 的颜色序列，支持两种操作：

  • 单点修改；
  • 区间数颜色；

数颜色有一种常用的技巧：维护 \(pre[i]\) 表示 \(a[i]\) 左侧和它颜色相同的最靠右的位置。

  • 修改时，我们使用 set 维护每一种颜色出现的所有位置，找到发生改变的 \(O(1)\) 个 pre，进行修改即可；
  • 查询时，我们只需要查询 \([l,r]\) 中有多少个 \(pre[i]<l\) 即可。

这是一类在线二维数点问题，可以离线并使用 cdq 分治解决（按时间排序，对 \(pre[i]\) 和 \(l\) 分治，使用树状数组维护序列下标）。

技巧

查询区间颜色数量，可以考虑维护 pre 数组并使用二维数点解决。

代码 
  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
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define cint const int &
#define re register
using namespace std;
const int N = 3E5 + 10;

struct Op {
    int tp, x, y, w, id;
    inline Op(int _t = 0, int _x = 0, int _y = 0, int _w = 0, int _id = 0) : 
        tp(_t), x(_x), y(_y), w(_w), id(_id) {}
};

int n, m;
int a[N], pre[N], ans[N];

int num[N], nn;

set<int> pos[N];
vector<Op> op;
Op q[N];

namespace BIT {
    int sum[N];
    inline int lowbit(cint x) { return x & -x; }
    inline void modify(cint p, cint v) {
        for(re int i = p + 1; i <= n + 2; i += lowbit(i)) sum[i] += v;
    }
    inline int query(cint l, cint r) {
        int res = 0;
        for(re int i = r + 1; i > 0; i -= lowbit(i)) res += sum[i];
        for(re int i = l; i > 0; i -= lowbit(i)) res -= sum[i];
        return res;
    }
    inline void clear(cint p) {
        for(re int i = p + 1; i <= n + 2; i += lowbit(i)) sum[i] = 0;
    }
};

void lisanhua() {
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
    }
    for(int i = 1; i <= m; i++) {
        if(q[i].tp == 0) continue;
        q[i].y = lower_bound(num + 1, num + 1 + nn, q[i].y) - num;
    }
}

void add_modify(int p, int v) {
    op.push_back({1, p, pre[p], -1});
    op.push_back({1, p, v, 1});
    pre[p] = v;
}

void add_query(int l, int r, int id) {
    op.push_back({0, l, r, l - 1, id});
}

void cdq(int l, int r, vector<Op> &op) {
    if(op.empty()) return;
    if(l == r) {
        for(Op &o : op) {
            if(o.tp == 1) BIT::modify(o.x, o.w);
            else ans[o.id] += BIT::query(o.x, o.y);
        }
        for(Op &o : op) {
            if(o.tp == 1) BIT::clear(o.x);
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<Op> lop, rop;
    for(Op &o : op) {
        if(o.tp == 1 && o.y <= mid) BIT::modify(o.x, o.w);
        if(o.tp == 0 && o.w > mid) ans[o.id] += BIT::query(o.x, o.y);
    }
    for(Op &o : op) {
        if(o.tp == 1 && o.y <= mid) BIT::clear(o.x);
    }
    for(Op &o : op) {
        if(o.tp == 1) {
            if(o.y <= mid) lop.push_back(o);
            else rop.push_back(o);
        } else {
            if(o.w <= mid) lop.push_back(o);
            else rop.push_back(o);
        }
    }
    cdq(l, mid, lop);
    cdq(mid + 1, r, rop);
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        num[++nn] = a[i];
    }
    for(int i = 1; i <= m; i++) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if(c == 'R') {
            q[i] = {1, x, y};
            num[++nn] = y;
        } else {
            q[i] = {0, x, y};
        }
    }

    lisanhua();

    for(int i = 1; i <= nn; i++) pos[i].insert(0);
    for(int i = 1; i <= n; i++) {
        pre[i] = *pos[a[i]].rbegin();
        pos[a[i]].insert(i);
    }
    for(int i = 1; i <= nn; i++) pos[i].insert(n + 1);
    for(int i = 1; i <= n; i++) {
        op.push_back({1, i, pre[i], 1});
    }

    for(int i = 1; i <= m; i++) {
        int x = q[i].x, y = q[i].y;
        if(q[i].tp == 1) {
            if(a[x] == y) continue;
            set<int>::iterator pr, nx;
            nx = pos[a[x]].upper_bound(x);
            if(*nx != n + 1) add_modify(*nx, pre[x]);
            pos[a[x]].erase(x);
            a[x] = y;
            nx = pos[y].upper_bound(x);
            --(pr = nx);
            add_modify(x, *pr);
            if(*nx != n + 1) add_modify(*nx, x);
            pos[y].insert(x);
        } else {
            add_query(x, y, i);
        }
    }

    cdq(0, n, op);

    for(int i = 1; i <= m; i++) {
        if(q[i].tp == 0) cout << ans[i] << '\n';
    }

    return 0;
}

P4396 [AHOI2013] 作业

题意

给定一个长度为 \(n\) 的序列 \(x\)；有 \(m\) 次询问，每次询问给定 \(l,r,a,b\)，询问序列区间 \([l,r]\) 中有多少个 \(i\) 满足 \(x_i\in [a,b]\)；以及有多少个不同的 \(x_i\in [a,b]\)。

\(n,m\le 10^5\)

第一问是二维数点板子。第二问是静态区间数颜色+值域约束，记录 \(pre\) 后三位偏序即可。

注意值域范围

\(pre\) 数组的值域是 \([0,n-1]\)，并且差分时也会产生一些 \(key=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
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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;

struct fast_istream {
    char ch;
    template<typename _Tp>
    inline fast_istream& operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct fast_ostream {
    int buf[60], nb;
    inline fast_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
    template<typename _Tp>
    inline fast_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
} fout;

struct Op {
    int tp, k1, k2, k3, w, id;
    inline bool operator<(const Op& other) const {
        if(k1 != other.k1) return k1 < other.k1;
        return tp > other.tp;
    }
};

int n, m;
int a[N], pre[N], lst[N];

int ans[2 * N];

int swp[5 * N], tmp[5 * N], nop1, nop2;
Op op1[5 * N], op2[5 * N];

namespace BIT {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void add(int p) {
        for(int i = p; i <= n; i += lowbit(i)) ++sum[i];
    }
    inline void clear(int p) {
        for(int i = p; i <= n; i += lowbit(i)) sum[i] = 0;
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
}

void cdq(Op* op, int l, int r, int ql, int qr) {
    if(ql > qr) return;
    if(l == r) {
        for(int i = ql; i <= qr; i++) {
            Op &o = op[swp[i]];
            if(o.tp == 1) BIT::add(o.k2);
            else ans[o.id] += o.w * BIT::query(o.k2);
        }
        for(int i = ql; i <= qr; i++) {
            Op &o = op[swp[i]];
            if(o.tp == 1) BIT::clear(o.k2);
        }
        return;
    }
    int mid = (l + r) >> 1;
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.tp == 1 && o.k3 <= mid) BIT::add(o.k2);
        else if(o.tp == 0 && o.k3 > mid) ans[o.id] += o.w * BIT::query(o.k2);
    }
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.tp == 1 && o.k3 <= mid) BIT::clear(o.k2);
    }
    int nql = ql - 1, nqr = qr + 1;
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.k3 <= mid) tmp[++nql] = swp[i];
    }
    for(int i = qr; i >= ql; i--) {
        Op &o = op[swp[i]];
        if(o.k3 > mid) tmp[--nqr] = swp[i];
    }
    for(int i = ql; i <= qr; i++) swp[i] = tmp[i];
    if(nql != nqr - 1) throw -1;
    cdq(op, l, mid, ql, nql);
    cdq(op, mid + 1, r, nqr, qr);
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];
    for(int i = 1; i <= m; i++) {
        int l, r, a, b, i1 = 2 * i - 1, i2 = i * 2;
        fin >> l >> r >> a >> b;
        op1[++nop1] = {0, r, b, 0, 1, i1};
        op1[++nop1] = {0, l - 1, b, 0, -1, i1};
        op1[++nop1] = {0, r, a - 1, 0, -1, i1};
        op1[++nop1] = {0, l - 1, a - 1, 0, 1, i1};
        op2[++nop2] = {0, r, b, l - 1, 1, i2};
        op2[++nop2] = {0, l - 1, b, l - 1, -1, i2};
        op2[++nop2] = {0, r, a - 1, l - 1, -1, i2};
        op2[++nop2] = {0, l - 1, a - 1, l - 1, 1, i2};
    }

    for(int i = 1; i <= n; i++) {
        pre[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        op1[++nop1] = {1, i, a[i], 0, 1, 0};
        op2[++nop2] = {1, i, a[i], pre[i], 1, 0};
    }

    sort(op1 + 1, op1 + 1 + nop1);
    sort(op2 + 1, op2 + 1 + nop2);

    for(int i = 1; i <= nop2; i++) swp[i] = i;
    cdq(op1, 0, 0, 1, nop1);
    for(int i = 1; i <= nop2; i++) swp[i] = i;
    cdq(op2, 0, n - 1, 1, nop2);

    for(int i = 1; i <= m; i++) {
        fout << ans[i * 2 - 1] << ' ' << ans[2 * i] << '\n';
    }

    return 0;
}

P4690 [Ynoi Easy Round 2016] 镜中的昆虫

详见我的题解。