离散化经常和sort 、unique 、erase 以及lower_bound 一起出现。它们看起来是几个不同的知识点,实际使用时却通常连成一套固定流程:
将需要处理的数复制出来;
排序并去重;
用二分查找每个数在去重数组中的位置;
用这个位置代替原来的数值。
这套操作常用于数值范围很大、实际出现的数却不多,并且题目只关心大小关系的情况。树状数组统计逆序对、扫描线、区间计数中都能见到它。
STL中的sort、unique 与 erase
先从一个普通的数组开始:
如果想删掉重复数字,通常先进行排序:
1 sort (a.begin (), a.end ());
排序后得到:
为什么一定要先排序?因为unique 只会处理相邻的重复元素。排序以后,相同数字会自然聚在一起,才能一次完成去重。
unique 做了什么?
unique 会保留每一段连续相同元素中的第一个,并把这些保留下来的元素移动到容器前面。它的返回值是“去重后有效区间的下一个位置”,也就是新的逻辑结尾。
1 auto it = unique (a.begin (), a.end ());
执行后,数组前半段已经是:
但此时 a.size() 没有改变。unique 只整理元素,不负责缩短 vector ,所以还要把 it 到原结尾这一段真正删除。
erase 如何删除元素?
对于 vector ,常见的两种删除方式如下:
1 2 a.erase (a.begin () + p); a.erase (a.begin () + l, a.begin () + r);
第二种写法仍然是左闭右开区间。删除以后,后面的元素会整体向前移动,因此单次 erase 的最坏时间复杂度是 O ( n ) O(n) O ( n ) 。
把 unique 返回的新结尾交给 erase ,就是最常见的排序去重写法:
1 2 sort (a.begin (), a.end ());a.erase (unique (a.begin (), a.end ()), a.end ());
执行后,原数组会真正变成:
如果使用的是普通数组,没有 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 x 的位置
第一个不小于x x x 的位置
upper_bound
第一个严格大于x x x 的位置
跳过所有小于等于x x x 的元素
假设数组已经排好序:
1 2 下标:0 1 2 3 4 5 数值:1 2 2 2 5 8
查找 x = 2 x=2 x = 2 时:
lower_bound 返回下标 1 1 1 ,指向第一个 2 2 2 ;
upper_bound 返回下标 4 4 4 ,指向第一个大于 2 2 2 的数 5 5 5 ;
两个位置相减得到 4 − 1 = 3 4-1=3 4 − 1 = 3 ,刚好是数字 2 2 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 (); int le = upper_bound (a.begin (), a.end (), x) - a.begin (); int eq = upper_bound (a.begin (), a.end (), x) - lower_bound (a.begin (), a.end (), x);
如果想统计有序数组中位于闭区间 [ l , r ] [l,r] [ l , r ] 的元素数量,可以写成:
1 2 int cnt = upper_bound (a.begin (), a.end (), r) - lower_bound (a.begin (), a.end (), l);
左边使用lower_bound (l l l ),跳过所有小于 l l l 的数;右边使用upper_bound (r r r ),包含所有等于 r r r 的数。二者之间就是 [ l , r ] [l,r] [ l , r ] 内的元素。
如何判断一个数是否存在?
lower_bound 返回的是应该插入的位置,不保证这个位置的值一定等于 x x x 。当 x x x 大于数组中的所有元素时,它还会返回 a.end() 。
因此判断元素是否存在时,需要同时检查迭代器没有到达结尾,并且它指向的值确实等于 x x 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 ) O(\log n) O ( log n ) 。如果使用 set 或 map ,应优先调用容器自己的 lower_bound 与 upper_bound 成员函数。
离散化
考虑下面的数组:
1 1000000000 -7 1000000000 42
数值范围很大,无法直接把它们当成数组下标。但是这个数组实际只有三种不同的值。如果题目只关心相等关系和大小关系,就可以把每个数替换成它在所有不同数值中的排名:
原数值
排名
− 7 -7 − 7
1 1 1
42 42 42
2 2 2
1000000000 1000000000 1000000000
3 3 3
于是原数组被转换为:
这个过程就是离散化。它保留了两件最重要的信息:
相等的数离散化以后仍然相等;
原来更小的数,离散化以后排名也更小。
原数值之间具体相差多少则不会保留。例如 − 7 -7 − 7 与 42 42 42 相差 49 49 49 ,离散化后的 1 1 1 与 2 2 2 只相差 1 1 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 是为了得到从 1 1 1 开始的排名。树状数组、线段树等数据结构通常使用从 1 1 1 开始的下标,所以这种写法最常见。如果后续算法可以使用下标 0 0 0 ,也可以不加 1 1 1 ,但整份代码必须统一。
下面给出一份完整模板。输入一个数组,输出每个元素离散化后的排名。
样例输入
样例输出
点击展开完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #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 1 1 开始的排名,所以访问 b 时需要减 1 1 1 。
这种写法通常属于离线离散化:开始计算以前,要先收集所有可能用到的值。如果后续操作还会产生此前没有收集的新值,插入它可能改变其他元素的排名,原来的映射就会失效。遇到真正在线产生的新值时,需要改用 map 、平衡树等能够动态维护有序关系的结构。
整套离散化的排序过程为 O ( n log n ) O(n\log n) O ( n log n ) ,每次查找排名为 O ( log n ) O(\log n) O ( log n ) ,把 n n n 个元素全部转换完成仍然是 O ( n log n ) O(n\log n) O ( n log n ) 。排序去重数组与保存原数组都需要 O ( n ) O(n) O ( n ) 空间。
常见模型与例题
前面的函数本身并不复杂,真正容易出错的是题目中的“严格”和“不严格”应该对应哪一个边界。下面五道题从直接调用二分函数开始,逐步过渡到离散化与其他数据结构的结合。
题目
核心操作
需要注意的边界
AtCoder ABC036 C
排序、去重、离散化
从 0 0 0 开始编号
Codeforces 600B
统计小于等于x x x
upper_bound(x)
洛谷 P1102
统计等于x x x
upper_bound(x)-lower_bound(x)
AtCoder ABC077 C
统计严格小于与严格大于
lower_bound 与upper_bound 配合
洛谷 P1955
离散化与并查集
先处理相等,再检查不等
例题一:AtCoder ABC036 C - 座圧
题目链接:AtCoder ABC036 C - 座圧
题目给出一个长度为n n n 的序列,要求在保持相等关系与大小关系的前提下,把所有数替换为从0 0 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 0 0 开始编号,所以lower_bound 返回的位置可以直接作为答案,不需要再加1 1 1 :
1 int id = lower_bound (b.begin (), b.end (), a[i]) - b.begin ();
如果后续接的是树状数组,就通常需要改成从1 1 1 开始;如果只是保存排名,使用从0 0 0 开始的编号完全没有问题。离散化的起点并没有固定规定,重要的是整份代码保持统一。
点击展开完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #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 log n ) ,每个元素进行一次二分,总时间复杂度仍为O ( n log n ) O(n\log n) O ( n log n ) ;两个数组的空间复杂度为O ( n ) O(n) O ( n ) 。
例题二:Codeforces 600B Queries about less or equal elements
题目链接:Codeforces 600B - Queries about less or equal elements
给定两个数组a a a 和b b b 。对于每个b j b_j b j ,需要求出a a a 中有多少个元素小于等于b j b_j b j 。
先将a a a 排序。对于一次询问x x x ,upper_bound(x) 指向第一个严格大于x x x 的位置,因此从数组开头到这个位置之前的所有元素都小于等于x x x :
1 int cnt = upper_bound (a.begin (), a.end (), x) - a.begin ();
这里不能凭感觉换成lower_bound 。假设:
lower_bound(5) 指向5 5 5 本身,它前面只有1 , 3 1,3 1 , 3 ,统计的是严格小于5 5 5 的数量;upper_bound(5) 指向7 7 7 ,它前面的1 , 3 , 5 1,3,5 1 , 3 , 5 才全部满足小于等于5 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 #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(n\log n) O ( n log n ) ,每个询问需要O ( log n ) O(\log n) O ( log n ) ,因此总时间复杂度为O ( n log n + m log n ) O(n\log n+m\log n) O ( n log n + m log n ) ,空间复杂度为O ( n ) O(n) O ( n ) 。
例题三:洛谷 P1102 A-B 数对
题目链接:洛谷 P1102 A-B 数对
给定一个长度为n n n 的序列和常数C C C ,要求统计满足下面条件的数对数量:
A − B = C A-B=C
A − B = C
将式子移项:
A = B + C A=B+C
A = B + C
于是可以枚举每一个B B B 。设当前枚举到的值为x x x ,只需要统计数组中有多少个数等于x + C x+C x + C 。
有序数组中等于y y y 的元素一定构成一段连续区间。这段区间的左端点是lower_bound(y) ,右端点的下一个位置是upper_bound(y) ,二者相减就是y 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 x x 作为B B B 出现了p p p 次,数值x + C x+C x + C 作为A A A 出现了q q q 次,那么枚举这p p p 个B B B 时,每次都会找到q q q 个A A A ,最终自然产生p q pq pq 个数对。
答案最多达到O ( n 2 ) O(n^2) O ( n 2 ) ,即使每个a i a_i a i 可以使用int 保存,答案也必须使用i64 。同时使用i64 保存a i a_i a i 和C C C ,可以避免计算x + C x+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 #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 n n 次二分的总时间复杂度为O ( n log n ) O(n\log n) O ( n log n ) ,空间复杂度为O ( n ) O(n) O ( n ) 。
例题四:AtCoder ABC077 C - Snuke Festival
题目链接:AtCoder ABC077 C - Snuke Festival
给定三个长度均为n n n 的数组A , B , C A,B,C A , B , C ,要求统计满足下面条件的三元组( i , j , k ) (i,j,k) ( i , j , k ) 数量:
A i < B j < C k A_i<B_j<C_k
A i < B j < C k
如果直接枚举三个位置,时间复杂度为O ( n 3 ) O(n^3) O ( n 3 ) 。更合适的做法是枚举中间值B j B_j B j ,分别计算它左边和右边可以选择多少个数。
对于当前值x = B j x=B_j x = B j :
L ( x ) = ∣ { A i ∣ A i < x } ∣ L(x)=\left|\left\lbrace A_i\mid A_i<x\right\rbrace\right|
L ( x ) = ∣ { A i ∣ A i < x } ∣
R ( x ) = ∣ { C k ∣ C k > x } ∣ R(x)=\left|\left\lbrace C_k\mid C_k>x\right\rbrace\right|
R ( x ) = ∣ { C k ∣ C k > x } ∣
左侧需要严格小于x x x 。将A A A 排序后,lower_bound(x) 前面的元素全部小于x x x :
1 i64 l = lower_bound (a.begin (), a.end (), x) - a.begin ();
右侧需要严格大于x x x 。将C C C 排序后,upper_bound(x) 会跳过所有小于等于x x x 的元素:
1 i64 r = c.end () - upper_bound (c.begin (), c.end (), x);
左边的每一种选择都能与右边的每一种选择组成一个三元组,因此当前x x x 产生的方案数为L ( x ) R ( x ) L(x)R(x) L ( x ) R ( x ) :
这道题的两个不等号都是严格不等号。A i = B j A_i=B_j A i = B j 或B j = C k B_j=C_k 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 #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 ) O(n\log n) O ( n log n ) ,枚举B B B 并进行两次二分同样需要O ( n log n ) O(n\log n) O ( n log n ) ,总时间复杂度为O ( n log n ) O(n\log n) O ( n log n ) ,空间复杂度为O ( n ) O(n) O ( n ) 。
例题五:洛谷 P1955 程序自动分析
题目链接:洛谷 P1955 程序自动分析
题目给出若干个形如x i = x j x_i=x_j x i = x j 或x i ≠ x j x_i\ne x_j x i = x j 的约束,要求判断这些条件能否同时成立。
相等关系具有传递性。如果x 1 = x 2 x_1=x_2 x 1 = x 2 且x 2 = x 3 x_2=x_3 x 2 = x 3 ,那么x 1 , x 2 , x 3 x_1,x_2,x_3 x 1 , x 2 , x 3 应该属于同一个集合,因此可以使用并查集维护所有相等关系。
但是变量编号最大可以达到10 9 10^9 1 0 9 ,无法直接把原编号当成并查集下标。每组约束只会出现两个编号,总共最多收集2 n 2n 2 n 个数,所以可以先把所有实际出现的编号离散化。
读入时同时保存约束和编号:
1 2 3 q[i] = {x, y, e}; b.push_back (x); b.push_back (y);
然后对b b b 排序去重。这里并查集可以正常使用下标0 0 0 ,所以映射时不必加1 1 1 :
1 int id = lower_bound (b.begin (), b.end (), x) - b.begin ();
接下来不能按照输入顺序边合并边检查。某条不等关系出现时,后面可能还有相等关系把两个集合连接起来。因此应该分成两步:
处理所有e = 1 e=1 e = 1 的约束,使用join 合并相等变量;
处理所有e = 0 e=0 e = 0 的约束,如果两个变量已经属于同一集合,说明条件矛盾。
例如:
1 2 3 x1 != x3 x1 == x2 x2 == x3
如果读到第一行就立即判断,会暂时认为x 1 x_1 x 1 和x 3 x_3 x 3 不在同一集合;但处理完后两行后可以推出x 1 = x 3 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 #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(n\log n) O ( n log n ) ,并查集操作的均摊复杂度接近O ( 1 ) O(1) O ( 1 ) ,所以总时间复杂度为O ( n log n + n α ( n ) ) O(n\log n+n\alpha(n)) O ( n log n + n α ( n )) ,通常直接写作O ( n log n ) O(n\log n) O ( n log n ) ;约束数组、离散化数组和并查集的空间复杂度均为O ( n ) O(n) O ( n ) 。
总结与常见问题
常见问题
unique 前为什么通常要 sort? 因为 unique 只能合并相邻的相同元素,不排序就只能去掉原本已经挨在一起的重复项。
为什么 unique 后数组长度没有变化? 它只返回新的逻辑结尾;对 vector 还要配合 erase 真正删除尾部内容。
lower_bound 找不到 x 时返回什么? 它返回 x x x 应该插入的位置,可能是中间某处,也可能是 end ,所以判断存在性时还要比较元素是否等于 x x x 。
lower_bound 和 upper_bound 最容易混淆在哪里? 前者允许等于,寻找第一个 ≥ x \ge x ≥ x 的位置;后者必须严格大于,寻找第一个 > x >x > x 的位置。
离散化后为什么有时要加 1? 是否加 1 1 1 取决于后续算法的下标习惯。树状数组不能使用下标 0 0 0 ,所以一般采用从 1 1 1 开始的排名。
离散化能不能保留数值之间的差? 不能。它只保留相等关系和大小顺序,涉及真实距离、区间长度时仍要使用原数值。
离散化以后还能随时加入新值吗? 普通离散化不能保证已有排名不变,所以应当提前收集所有可能出现的值。
统计严格小于和小于等于时分别用什么? 严格小于x x x 的数量使用lower_bound(x) ,小于等于x x x 的数量使用upper_bound(x) 。
为什么计数题经常需要 i64? 单个元素和单次计数可能没有超过int ,但数对或三元组数量可能达到O ( n 2 ) O(n^2) O ( n 2 ) 甚至O ( n 3 ) O(n^3) O ( n 3 ) 。
复杂度分析
sort :时间复杂度 O ( n log n ) O(n\log n) O ( n log n ) 。
unique :时间复杂度 O ( n ) O(n) O ( n ) ,不会改变容器大小。
vector::erase :最坏时间复杂度 O ( n ) O(n) O ( n ) 。
lower_bound、upper_bound :在数组或 vector 上为 O ( log n ) O(\log n) O ( log n ) 。
完成 n n n 个元素的离散化:时间复杂度 O ( n log n ) O(n\log n) O ( n log n ) ,空间复杂度 O ( n ) O(n) O ( n ) 。