离散化经常和sort、unique、erase以及lower_bound一起出现。它们看起来是几个不同的知识点，实际使用时却通常连成一套固定流程：

  1. 将需要处理的数复制出来；
  2. 排序并去重；
  3. 用二分查找每个数在去重数组中的位置；
  4. 用这个位置代替原来的数值。

这套操作常用于数值范围很大、实际出现的数却不多，并且题目只关心大小关系的情况。树状数组统计逆序对、扫描线、区间计数中都能见到它。

STL中的sort、unique 与 erase

先从一个普通的数组开始：

1
5 2 2 7 5 2

如果想删掉重复数字，通常先进行排序：

1
sort(a.begin(), a.end());

排序后得到：

1
2 2 2 5 5 7

为什么一定要先排序？因为unique只会处理相邻的重复元素。排序以后，相同数字会自然聚在一起，才能一次完成去重。

unique 做了什么？

unique会保留每一段连续相同元素中的第一个，并把这些保留下来的元素移动到容器前面。它的返回值是“去重后有效区间的下一个位置”，也就是新的逻辑结尾。

1
auto it = unique(a.begin(), a.end());

执行后，数组前半段已经是：

1
2 5 7 | 后面的内容不再属于去重结果

但此时 a.size() 没有改变。unique只整理元素，不负责缩短 vector，所以还要把 it 到原结尾这一段真正删除。

erase 如何删除元素？

对于 vector，常见的两种删除方式如下：

1
2
a.erase(a.begin() + p);                    // 删除下标p处的一个元素
a.erase(a.begin() + l, a.begin() + r);     // 删除下标区间[l,r)

第二种写法仍然是左闭右开区间。删除以后，后面的元素会整体向前移动，因此单次 erase 的最坏时间复杂度是 $O(n)$。

把 unique 返回的新结尾交给 erase，就是最常见的排序去重写法：

1
2
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());

执行后，原数组会真正变成：

1
2 5 7

如果使用的是普通数组，没有 erase 成员函数，可以直接记录新的有效长度：

1
2
sort(a, a + n);
int m = unique(a, a + n) - a;

此时只有 a[0] 到 a[m - 1] 属于去重后的结果，后面的内容应当忽略。

需要注意，排序去重会改变元素原来的顺序。如果题目要求“保留第一次出现的顺序”，就不能直接使用这套写法，而应该用集合记录元素是否出现过，再按原顺序加入新的数组。

lower_bound 与 upper_bound

完成排序以后，就可以在有序序列上进行二分查找。C++提供的lower_bound和upper_bound不会直接告诉我们“有没有找到”，而是返回一个迭代器。

两者的定义一定要分清：

函数 返回位置 可以理解为
lower_bound 第一个大于等于$x$的位置 第一个不小于$x$的位置
upper_bound 第一个严格大于$x$的位置 跳过所有小于等于$x$的元素

假设数组已经排好序：

1
2
下标：0 1 2 3 4 5
数值：1 2 2 2 5 8

查找 $x=2$ 时：

  • lower_bound返回下标 $1$，指向第一个 $2$；
  • upper_bound返回下标 $4$，指向第一个大于 $2$ 的数 $5$；
  • 两个位置相减得到 $4-1=3$，刚好是数字 $2$ 的出现次数。

对应代码如下：

1
2
3
int l = lower_bound(a.begin(), a.end(), x) - a.begin();
int r = upper_bound(a.begin(), a.end(), x) - a.begin();
int cnt = r - l;

由定义还可以直接得到下面几种常用统计：

1
2
3
int lt = lower_bound(a.begin(), a.end(), x) - a.begin();        // 小于x的数量
int le = upper_bound(a.begin(), a.end(), x) - a.begin();        // 小于等于x的数量
int eq = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x); // 等于x的数量

如果想统计有序数组中位于闭区间 $[l,r]$ 的元素数量，可以写成：

1
2
int cnt = upper_bound(a.begin(), a.end(), r)
        - lower_bound(a.begin(), a.end(), l);

左边使用lower_bound($l$)，跳过所有小于 $l$ 的数；右边使用upper_bound($r$)，包含所有等于 $r$ 的数。二者之间就是 $[l,r]$ 内的元素。

如何判断一个数是否存在？

lower_bound返回的是应该插入的位置，不保证这个位置的值一定等于 $x$。当 $x$ 大于数组中的所有元素时，它还会返回 a.end()。

因此判断元素是否存在时，需要同时检查迭代器没有到达结尾，并且它指向的值确实等于 $x$：

1
2
auto it = lower_bound(a.begin(), a.end(), x);
bool exist = it != a.end() && *it == x;

不能在检查 it != a.end() 之前直接访问 *it，否则可能解引用尾迭代器。

上面所有写法都有一个共同前提：参与查找的区间必须有序。对于 vector 和普通数组，二分查找的时间复杂度是 $O(\log n)$。如果使用 set 或 map，应优先调用容器自己的 lower_bound 与 upper_bound 成员函数。

离散化

考虑下面的数组：

1
1000000000 -7 1000000000 42

数值范围很大，无法直接把它们当成数组下标。但是这个数组实际只有三种不同的值。如果题目只关心相等关系和大小关系，就可以把每个数替换成它在所有不同数值中的排名：

原数值 排名
$-7$ $1$
$42$ $2$
$1000000000$ $3$

于是原数组被转换为：

1
3 1 3 2

这个过程就是离散化。它保留了两件最重要的信息：

  1. 相等的数离散化以后仍然相等；
  2. 原来更小的数，离散化以后排名也更小。

原数值之间具体相差多少则不会保留。例如 $-7$ 与 $42$ 相差 $49$，离散化后的 $1$ 与 $2$ 只相差 $1$。因此，离散化适合处理排名、大小比较、出现次数等问题，不能直接拿离散化后的值计算原来的距离或差值。

标准写法

设原数组为 a，复制一份到 b 中。b负责保存排序去重后的原数值，a仍然保留原来的顺序。

1
2
3
vector<i64> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());

对于原数组中的每个 a[i]，使用lower_bound找到它在 b 中的位置：

1
int id = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;

这里加 $1$ 是为了得到从 $1$ 开始的排名。树状数组、线段树等数据结构通常使用从 $1$ 开始的下标，所以这种写法最常见。如果后续算法可以使用下标 $0$，也可以不加 $1$，但整份代码必须统一。

下面给出一份完整模板。输入一个数组，输出每个元素离散化后的排名。

样例输入

1
2
6
100 20 100 -5 20 70

样例输出

1
4 2 4 1 2 3
点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int get(const vector<i64>& b, i64 x) { return lower_bound(b.begin(), b.end(), x) - b.begin() + 1; }

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<i64> a(n), b;
    b.reserve(n);
    for (int i = 0; i < n; i++) { cin >> a[i]; b.push_back(a[i]); }

    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for (int i = 0; i < n; i++) cout << get(b, a[i]) << " \n"[i == n - 1];
    return 0;
}

如果已经知道离散化后的排名 id，也可以还原对应的原数值：

1
i64 x = b[id - 1];

因为本文使用的是从 $1$ 开始的排名，所以访问 b 时需要减 $1$。

这种写法通常属于离线离散化：开始计算以前，要先收集所有可能用到的值。如果后续操作还会产生此前没有收集的新值，插入它可能改变其他元素的排名，原来的映射就会失效。遇到真正在线产生的新值时，需要改用 map、平衡树等能够动态维护有序关系的结构。

整套离散化的排序过程为 $O(n\log n)$，每次查找排名为 $O(\log n)$，把 $n$ 个元素全部转换完成仍然是 $O(n\log n)$。排序去重数组与保存原数组都需要 $O(n)$ 空间。

常见模型与例题

前面的函数本身并不复杂，真正容易出错的是题目中的“严格”和“不严格”应该对应哪一个边界。下面五道题从直接调用二分函数开始，逐步过渡到离散化与其他数据结构的结合。

题目 核心操作 需要注意的边界
AtCoder ABC036 C 排序、去重、离散化 从 $0$ 开始编号
Codeforces 600B 统计小于等于$x$ upper_bound(x)
洛谷 P1102 统计等于$x$ upper_bound(x)-lower_bound(x)
AtCoder ABC077 C 统计严格小于与严格大于 lower_bound与upper_bound配合
洛谷 P1955 离散化与并查集 先处理相等，再检查不等

例题一：AtCoder ABC036 C - 座圧

题目链接：AtCoder ABC036 C - 座圧

题目给出一个长度为$n$的序列，要求在保持相等关系与大小关系的前提下，把所有数替换为从$0$开始的连续编号。

例如：

1
2
3
原序列：3 3 1 6 1
排序去重：1 3 6
离散化：1 1 0 2 0

这就是离散化最直接的形式。先复制原数组并排序去重，再查找每个原数值在去重数组中的位置。

1
2
3
vector<i64> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());

因为题目要求从$0$开始编号，所以lower_bound返回的位置可以直接作为答案，不需要再加$1$：

1
int id = lower_bound(b.begin(), b.end(), a[i]) - b.begin();

如果后续接的是树状数组，就通常需要改成从$1$开始；如果只是保存排名，使用从$0$开始的编号完全没有问题。离散化的起点并没有固定规定，重要的是整份代码保持统一。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<i64> a(n), b;
    for (int i = 0; i < n; i++) cin >> a[i];

    b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for (i64 x : a) cout << lower_bound(b.begin(), b.end(), x) - b.begin() << '\n';
    return 0;
}

排序的时间复杂度为$O(n\log n)$，每个元素进行一次二分，总时间复杂度仍为$O(n\log n)$；两个数组的空间复杂度为$O(n)$。

例题二：Codeforces 600B Queries about less or equal elements

题目链接：Codeforces 600B - Queries about less or equal elements

给定两个数组$a$和$b$。对于每个$b_j$，需要求出$a$中有多少个元素小于等于$b_j$。

先将$a$排序。对于一次询问$x$，upper_bound(x) 指向第一个严格大于$x$的位置，因此从数组开头到这个位置之前的所有元素都小于等于$x$：

1
int cnt = upper_bound(a.begin(), a.end(), x) - a.begin();

这里不能凭感觉换成lower_bound。假设：

1
2
a = 1 3 5 7 9
x = 5

lower_bound(5) 指向$5$本身，它前面只有$1,3$，统计的是严格小于$5$的数量；upper_bound(5) 指向$7$，它前面的$1,3,5$才全部满足小于等于$5$。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        int cnt = upper_bound(a.begin(), a.end(), x) - a.begin();
        cout << cnt << " \n"[i == m - 1];
    }
    return 0;
}

排序需要$O(n\log n)$，每个询问需要$O(\log n)$，因此总时间复杂度为$O(n\log n+m\log n)$，空间复杂度为$O(n)$。

例题三：洛谷 P1102 A-B 数对

题目链接：洛谷 P1102 A-B 数对

给定一个长度为$n$的序列和常数$C$，要求统计满足下面条件的数对数量：

$$
A-B=C
$$

将式子移项：

$$
A=B+C
$$

于是可以枚举每一个$B$。设当前枚举到的值为$x$，只需要统计数组中有多少个数等于$x+C$。

有序数组中等于$y$的元素一定构成一段连续区间。这段区间的左端点是lower_bound(y)，右端点的下一个位置是upper_bound(y)，二者相减就是$y$的出现次数：

1
2
3
auto l = lower_bound(a.begin(), a.end(), x + c);
auto r = upper_bound(a.begin(), a.end(), x + c);
ans += r - l;

重复数字不需要单独分类。假设数值$x$作为$B$出现了$p$次，数值$x+C$作为$A$出现了$q$次，那么枚举这$p$个$B$时，每次都会找到$q$个$A$，最终自然产生$pq$个数对。

答案最多达到$O(n^2)$，即使每个$a_i$可以使用int保存，答案也必须使用i64。同时使用i64保存$a_i$和$C$，可以避免计算$x+C$时越界。

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    i64 c;
    cin >> n >> c;
    vector<i64> a(n);
    for (i64& x : a) cin >> x;
    sort(a.begin(), a.end());

    i64 ans = 0;
    for (i64 x : a) {
        auto l = lower_bound(a.begin(), a.end(), x + c);
        auto r = upper_bound(a.begin(), a.end(), x + c);
        ans += r - l;
    }
    cout << ans << '\n';
    return 0;
}

排序与$n$次二分的总时间复杂度为$O(n\log n)$，空间复杂度为$O(n)$。

例题四：AtCoder ABC077 C - Snuke Festival

题目链接：AtCoder ABC077 C - Snuke Festival

给定三个长度均为$n$的数组$A,B,C$，要求统计满足下面条件的三元组$(i,j,k)$数量：

$$
A_i<B_j<C_k
$$

如果直接枚举三个位置，时间复杂度为$O(n^3)$。更合适的做法是枚举中间值$B_j$，分别计算它左边和右边可以选择多少个数。

对于当前值$x=B_j$：

$$
L(x)=\left|\left\lbrace A_i\mid A_i<x\right\rbrace\right|
$$

$$
R(x)=\left|\left\lbrace C_k\mid C_k>x\right\rbrace\right|
$$

左侧需要严格小于$x$。将$A$排序后，lower_bound(x) 前面的元素全部小于$x$：

1
i64 l = lower_bound(a.begin(), a.end(), x) - a.begin();

右侧需要严格大于$x$。将$C$排序后，upper_bound(x) 会跳过所有小于等于$x$的元素：

1
i64 r = c.end() - upper_bound(c.begin(), c.end(), x);

左边的每一种选择都能与右边的每一种选择组成一个三元组，因此当前$x$产生的方案数为$L(x)R(x)$：

1
ans += l * r;

这道题的两个不等号都是严格不等号。$A_i=B_j$或$B_j=C_k$时均不合法，这也是为什么左边使用lower_bound，右边使用upper_bound。

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    for (int& x : c) cin >> x;
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());

    i64 ans = 0;
    for (int x : b) {
        i64 l = lower_bound(a.begin(), a.end(), x) - a.begin();
        i64 r = c.end() - upper_bound(c.begin(), c.end(), x);
        ans += l * r;
    }
    cout << ans << '\n';
    return 0;
}

排序两个数组需要$O(n\log n)$，枚举$B$并进行两次二分同样需要$O(n\log n)$，总时间复杂度为$O(n\log n)$，空间复杂度为$O(n)$。

例题五：洛谷 P1955 程序自动分析

题目链接：洛谷 P1955 程序自动分析

题目给出若干个形如$x_i=x_j$或$x_i\ne x_j$的约束，要求判断这些条件能否同时成立。

相等关系具有传递性。如果$x_1=x_2$且$x_2=x_3$，那么$x_1,x_2,x_3$应该属于同一个集合，因此可以使用并查集维护所有相等关系。

但是变量编号最大可以达到$10^9$，无法直接把原编号当成并查集下标。每组约束只会出现两个编号，总共最多收集$2n$个数，所以可以先把所有实际出现的编号离散化。

读入时同时保存约束和编号：

1
2
3
q[i] = {x, y, e};
b.push_back(x);
b.push_back(y);

然后对$b$排序去重。这里并查集可以正常使用下标$0$，所以映射时不必加$1$：

1
int id = lower_bound(b.begin(), b.end(), x) - b.begin();

接下来不能按照输入顺序边合并边检查。某条不等关系出现时，后面可能还有相等关系把两个集合连接起来。因此应该分成两步：

  1. 处理所有$e=1$的约束，使用join合并相等变量；
  2. 处理所有$e=0$的约束，如果两个变量已经属于同一集合，说明条件矛盾。

例如：

1
2
3
x1 != x3
x1 == x2
x2 == x3

如果读到第一行就立即判断，会暂时认为$x_1$和$x_3$不在同一集合；但处理完后两行后可以推出$x_1=x_3$，此时才会发现矛盾。先完成所有相等关系的合并，就不会受输入顺序影响。

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

struct Q { i64 x, y; int e; };
vector<int> fa;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void join(int a, int b) { a = find(a); b = find(b); if (a != b) fa[a] = b; }

void solve() {
    int n;
    cin >> n;
    vector<Q> q(n);
    vector<i64> b;
    b.reserve(n * 2);

    for (auto& [x, y, e] : q) {
        cin >> x >> y >> e;
        b.push_back(x);
        b.push_back(y);
    }

    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    fa.resize(b.size());
    iota(fa.begin(), fa.end(), 0);

    auto get = [&](i64 x) { return lower_bound(b.begin(), b.end(), x) - b.begin(); };
    for (auto [x, y, e] : q) {
        if (e == 1) join(get(x), get(y));
    }

    for (auto [x, y, e] : q) {
        if (e == 0 && find(get(x)) == find(get(y))) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

每组数据的离散化需要$O(n\log n)$，并查集操作的均摊复杂度接近$O(1)$，所以总时间复杂度为$O(n\log n+n\alpha(n))$，通常直接写作$O(n\log n)$；约束数组、离散化数组和并查集的空间复杂度均为$O(n)$。

总结与常见问题

常见问题

  • unique 前为什么通常要 sort？ 因为 unique只能合并相邻的相同元素，不排序就只能去掉原本已经挨在一起的重复项。
  • 为什么 unique 后数组长度没有变化？ 它只返回新的逻辑结尾；对 vector还要配合 erase真正删除尾部内容。
  • lower_bound 找不到 x 时返回什么？ 它返回 $x$应该插入的位置，可能是中间某处，也可能是 end，所以判断存在性时还要比较元素是否等于 $x$。
  • lower_bound 和 upper_bound 最容易混淆在哪里？ 前者允许等于，寻找第一个 $\ge x$ 的位置；后者必须严格大于，寻找第一个 $>x$ 的位置。
  • 离散化后为什么有时要加 1？ 是否加 $1$取决于后续算法的下标习惯。树状数组不能使用下标 $0$，所以一般采用从 $1$开始的排名。
  • 离散化能不能保留数值之间的差？ 不能。它只保留相等关系和大小顺序，涉及真实距离、区间长度时仍要使用原数值。
  • 离散化以后还能随时加入新值吗？ 普通离散化不能保证已有排名不变，所以应当提前收集所有可能出现的值。
  • 统计严格小于和小于等于时分别用什么？ 严格小于$x$的数量使用lower_bound(x)，小于等于$x$的数量使用upper_bound(x)。
  • 为什么计数题经常需要 i64？ 单个元素和单次计数可能没有超过int，但数对或三元组数量可能达到$O(n^2)$甚至$O(n^3)$。

复杂度分析

  • sort：时间复杂度 $O(n\log n)$。
  • unique：时间复杂度 $O(n)$，不会改变容器大小。
  • vector::erase：最坏时间复杂度 $O(n)$。
  • lower_bound、upper_bound：在数组或 vector上为 $O(\log n)$。
  • 完成 $n$ 个元素的离散化：时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。