2 离散化三步法：排序 → 去重 → 二分映射 必背
这是本讲第一个必须背下来的模板。三步走完，任意一个大值域的数组都能被压成 [1, k] 的稠密编号。
▶ 离散化三步：处理数组 [1000000000, -5, 7, 1000000000, 3]
▶ 自动演示
↺ 重来
0 原始数组 ：a = [1000000000, −5, 7, 1000000000, 3]。值域约 ±10⁹，不能直接当数组下标。
1 第一步 · 排序 ：拷贝一份并 sort → [−5, 3, 7, 1000000000, 1000000000]。复杂度 O(n log n)。
2 第二步 · 去重 ：unique 把重复元素挪到末尾并返回新的逻辑结尾，再 erase 掉 → [−5, 3, 7, 1000000000]，共 k = 4 个不同的值。
3 第三步 · 二分映射 ：对每个元素用 lower_bound 在去重后的数组里查位置，加 1 变成 1-based 编号。
4 1000000000 → 下标 3 → 编号 4 ；−5 → 下标 0 → 编号 1 ；7 → 下标 2 → 编号 3 ；3 → 下标 1 → 编号 2 。
5 最终结果 ：b = [4, 1, 3, 4, 2]，值域从 ±10⁹ 压到 [1, 4]。相对大小完全保持：−5 < 3 < 7 < 10⁹ 对应 1 < 2 < 3 < 4 ✓
注意第三步的「加 1」：加不加取决于你的使用习惯。树状数组需要 1-based 下标，所以通常加 1；纯比较场景可以不加。
C++ 离散化标准模板（sort + unique + lower_bound）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005 ;
long long a[MAXN]; // 原始数据（值域可能很大，用 long long）
int b[MAXN]; // 离散化后的编号
vector <long long > v; // 去重后的候选值
void discretize(int n) {
v.assign(a + 1 , a + n + 1 ); // ① 拷贝一份
sort(v.begin(), v.end()); // ② 排序 O(n log n)
v.erase(unique(v.begin(), v.end()), v.end()); // ③ 去重
for (int i = 1 ; i <= n; i++)
b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1 ; // ④ 映射到 1..k
}
int main() {
ios::sync_with_stdio(0 ); cin.tie(0 );
int n; cin >> n;
for (int i = 1 ; i <= n; i++) cin >> a[i];
discretize(n);
cout << "不同值个数 k = " << v.size() << "\n" ;
for (int i = 1 ; i <= n; i++) cout << b[i] << " \n" [i == n];
// 反查：编号 → 原值
int id = b[1 ];
cout << "编号 " << id << " 对应原值 " << v[id - 1 ] << endl;
return 0 ;
}运行结果
输入: 5 / 1000000000 -5 7 1000000000 3
输出: 不同值个数 k = 4
编号序列 b = 4 1 3 4 2
编号 4 对应原值 1000000000
【复杂度】
排序 O(n log n) + n 次二分 O(n log n) = O(n log n)
空间 O(n)，与值域无关
【对比：直接开桶】
值域 ±10⁹ 需要 2×10⁹ 个 long long = 16 GB → MLE ❌
原值
原值
原值
原值
原序列
新序列
💭 为什么 unique 之后一定要 erase？
因为 unique 不会真正删除元素 ，它只是把不重复的元素依次搬到前面，并返回「新的逻辑结尾」这个迭代器，后面的位置仍然保留着旧的垃圾数据。如果只用 unique 不 erase，v.size() 仍然是原来的大小，后续 lower_bound 会在垃圾数据里查找，结果完全错乱。标准写法永远是这两句连用 ：
v.erase(unique(v.begin(), v.end()), v.end());
另一个常见坑 ：unique 只能去掉相邻 的重复元素，所以必须先排序。先 unique 后 sort 是无效的。
3 区间离散化：为什么必须把 r+1 也放进去 易错
当离散化的对象是区间 而不是点时，候选集合的选取会直接决定答案对不对。这里有一个几乎所有初学者都会踩的坑 —— 不同的题目语义，需要不同的候选集 。
📐 两种语义，两套候选集（关键）
区间离散化最容易出错的地方在于：先要确定题目要的是「连续长度」还是「整点计数」 ，两者的候选集与差分标记完全不同。
语义 A · 连续长度 ：区间 [l, r] 表示一段长度为 r − l 的连续线段。l 与 r ；差分写 d[l] += 1; d[r] -= 1;。
语义 B · 整点计数 ：区间 [l, r] 表示覆盖整数点 l, l+1, …, r 共 r − l + 1 个点。l 与 r+1 ；差分写 d[l] += 1; d[r+1] -= 1;。
为什么候选集必须这样放？ 因为离散化的前提是「每一小段内部性质完全一致」。对连续长度而言，性质会在 l 和 r 处改变（覆盖开始/结束），所以候选点是 l 与 r；对整点计数而言，性质在第 r 个点之后改变，所以候选点是 l 与 r+1。选错候选集，要么丢一个点，要么多算一段长度。
一句话记法 ：算长度放两端，数点数放「右边加一」。
对象类型 候选集合内容 差分标记位置 典型题目 点（判断相等/排名） 所有出现过的值 不需要差分 逆序对、统计不同数、排名 区间 · 求连续长度 所有 l 与所有 r d[l]++, d[r]--区间覆盖总长度、矩形面积并 区间 · 数整点个数 所有 l 与所有 r+1 d[l]++, d[r+1]--格点覆盖统计、染色问题 矩形（二维） x 方向放 x1、x2；y 方向放 y1、y2 事件为正负标记 矩形面积并、矩形覆盖统计
4 扫描线思想：把二维问题拆成一维 核心
扫描线 不是一个具体的数据结构，而是一种思考方式 ：既然二维平面上同时处理两个维度太困难，那就固定一个维度，让它「一格一格地走」，在每一步只处理一维的问题。
扫描线：当前事件位置 x
已扫过的宽度 dx
矩形 A
矩形 B
矩形 C
→ 竖直方向（y 轴）上，线段树随时维护「当前被覆盖的总长度 len」
扫描线三步曲
造事件 ：把每个矩形拆成两条竖边事件 —— 左边界 (x₁, y₁, y₂, +1) 表示「从这里开始覆盖」，右边界 (x₂, y₁, y₂, −1) 表示「到这里覆盖结束」。排事件 ：把所有 2n 个事件按 x 坐标升序排序。扫一遍 ：从左往右依次处理。相邻两个事件之间，x 方向没有变化，所以这段区域的面积就是 len × (xi+1 − xi ) ；处理完事件后更新线段树，进入下一段。
整张平面的面积 = 所有小条面积之和。二维问题，就被拆成了 2n 个一维问题。
扫描线要素 要回答的问题 本例的答案 扫描方向 沿哪一维推进？ 沿 x 轴从左到右（也可以选 y，思路完全对称） 事件定义 什么样的位置需要「停下来处理」？ 矩形的左边界与右边界，共 2n 个 事件排序 多个事件在同一坐标怎么办？ 先处理 −1 再处理 +1（或将同一 x 的事件合并处理后一次性统计） 状态维护 用什么记住「当前被覆盖了多长」？ 离散化 y 坐标 + 线段树（或有序集合） 贡献累计 每一段贡献多少答案？ len × dx，累加进总面积
📐 扫描线能解决哪些问题
① 矩形面积并 ：最经典的应用，状态是「覆盖长度」。复杂度 O(n log n)。
② 矩形周长并 ：状态是「覆盖长度」与「不相交的连续段个数」（用来统计水平边的条数）。比面积并多维护一个信息。
③ 天际线问题 ：状态是「当前最高建筑物的高度」。只需一个 multiset 就够了，不需要线段树。
④ 平面最近点对（分治的另一视角） ：按 x 排序后扫描，用「当前最优距离」约束 y 方向的搜索范围，本质上也是一种扫描线。
⑤ 二维数点 / 三维偏序 ：把其中一个维度当作扫描方向，另外的维度交给树状数组或 CDQ 分治。
选型提示 ：如果状态是「最大 / 最小值」，用 multiset 或堆；如果状态是「总长度 / 总个数」，用线段树或树状数组；如果状态是「是否存在」，用 set 或布尔数组。先想清楚状态是什么，再选数据结构。
5 区间覆盖长度：扫描线的「一维预演」 入门
在看矩形之前，先做一个一维的小问题：给定 n 个区间 [l, r]，求它们并集的总长度 。这个问题是矩形面积并的「降维版」，思路一模一样。
方法一 · 排序 + 合并 推荐
把所有区间按左端点排序，然后维护一个「当前合并段的右端点」。如果下一个区间的左端点 ≤ 当前右端点，就合并；否则结算当前段并开启新段。复杂度 O(n log n)（排序）。
方法二 · 离散化 + 差分 扫描线视角
把所有的 l 与 r+1 离散化，得到一串编号；用差分数组在 l 处 +1、r+1 处 −1；最后做前缀和，凡是「计数 > 0」的相邻两编号之间的真实长度都要累加。值域小的时候可以不离散化，直接开差分数组。
C++ 两种方法对比：合并法与扫描线差分法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* ============ 方法一：排序 + 合并，O(n log n) ============ */
ll mergeLen(vector<pair<ll,ll>> seg) {
sort(seg.begin(), seg.end());
ll total = 0 , L = seg[0 ].first, R = seg[0 ].second;
for (size_t i = 1 ; i < seg.size(); i++) {
if (seg[i].first <= R) // 有重叠或相接，合并
R = max(R, seg[i].second);
else {
total += R - L; // 结算当前段
L = seg[i].first; R = seg[i].second;
}
}
return total + (R - L); // 别忘了最后一段
}
/* ============ 方法二：离散化 + 差分（连续长度语义），O(n log n) ============ */
ll diffLen(vector<pair<ll,ll>> seg) {
vector<ll> v;
for (auto &s : seg) { v.push_back(s.first); v.push_back(s.second); } // 连续长度：放 l 与 r
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int m = v.size();
vector<int > d(m + 2 , 0 );
for (auto &s : seg) {
int l = lower_bound(v.begin(), v.end(), s.first) - v.begin();
int r = lower_bound(v.begin(), v.end(), s.second) - v.begin();
d[l]++; d[r]--; // 差分标记：左端 +1，右端 −1
}
ll total = 0 ; int cur = 0 ;
for (int i = 0 ; i + 1 < m; i++) {
cur += d[i]; // 前缀和 = 当前这段被几个区间覆盖
if (cur > 0 ) total += v[i + 1 ] - v[i]; // 累加真实长度，不是 1！
}
return total;
}
int main() {
vector<pair<ll,ll>> seg = {{1, 3}, {2, 6}, {8, 10}, {9, 12}};
cout << "合并法 : " << mergeLen(seg) << endl;
cout << "差分扫描 : " << diffLen(seg) << endl;
return 0 ;
}运行结果
输入区间: [1,3] [2,6] [8,10] [9,12]
合并法 : 9
差分扫描 : 9 ✅ 两者一致
手算验证（连续长度语义，长度 = r − l）:
[1,3] ∪ [2,6] = [1,6] 长度 6 − 1 = 5
[8,10] ∪ [9,12] = [8,12] 长度 12 − 8 = 4
总计 5 + 4 = 9 ✓
差分扫描的逐步过程:
候选值 v = [1, 2, 3, 6, 8, 9, 10, 12]，共 7 段
段 [1,2] 覆盖数 1 → +1
段 [2,3] 覆盖数 2 → +1
段 [3,6] 覆盖数 1 → +3
段 [6,8] 覆盖数 0 → +0
段 [8,9] 覆盖数 1 → +1
段 [9,10] 覆盖数 2 → +1
段 [10,12] 覆盖数 1 → +2
合计 1+1+3+0+1+1+2 = 9 ✓
【复杂度】
合并法 : O(n log n)（排序主导），O(n) 空间
差分扫描 : O(n log n)（排序主导），O(n) 空间
💭 两种方法该怎么选？
合并法 更适合「独立区间集合」的场景 —— 每段区间是独立的一块，合并过程一目了然，代码短、常数小。差分扫描法 更像扫描线的雏形：它天然支持「统计被覆盖 k 次的长度」这类升级需求（只要把判断条件从 cur > 0 改成 cur >= k），而合并法要实现这个就非常别扭。
更重要的原因 ：当问题从一维升级到二维（矩形面积并），合并法彻底失效，而扫描线 + 线段树的框架可以平滑扩展。所以先练熟差分扫描，就是为二维做铺垫。
最后再强调一次语义 ：本讲的代码统一采用连续长度 语义（长度 = r − l）。如果题目给的是「整数点 [l, r]」，请把候选集改成 {l} ∪ {r+1}，差分改成 d[l]++, d[r+1]--，其他部分完全不变。
6 矩形面积并：扫描线 + 线段树维护覆盖长度 提高核心
现在把「区间覆盖」升级到二维：给定 n 个矩形，求它们覆盖的总面积（重叠部分只算一次）。n ≤ 10⁵。
📐 从暴力到正解的三级跳
方法一 · 二维差分 只能用于小值域 ：值域 ≤ 10³ 时可以开二维数组打标记，然后前缀和统计。值域 10⁹ 时内存爆炸，不可行 。
方法二 · 离散化二维差分 O(n³) 常数大 ：把 x、y 各离散化成 ≤ 2n 个编号，开 2n × 2n 的差分数组。空间 O(n²)，时间 O(n²)。n = 10⁵ 时 4×10¹⁰ 也不行，但 n ≤ 1000 时可用。
方法三 · 扫描线 + 线段树 正解 O(n log n) ：沿 x 扫描，线段树在 y 方向上维护「当前被覆盖的总长度 len」。每扫过一段宽度 dx，面积就增加 len × dx。共 2n 个事件，每个事件做一次线段树更新 O(log n) → 总复杂度 O(n log n)。
线段树的特殊设计（重要） ：这棵树每个节点维护两个值：
字段 含义 维护方式 cnt[p] 该节点对应区间被「完整覆盖」的次数 区间修改时直接 cnt[p] += k，不向下传递 len[p] 该节点对应区间中被覆盖的真实长度 见下面的 pushup 三分支
C++ 整棵树的核心：pushup 函数只有三个分支
void pushup(int p, int l, int r) {
if (cnt[p] > 0 ) {
// 分支一：整个区间被完整覆盖，len 就是它的真实长度
len[p] = ys[r + 1 ] - ys[l];
} else if (l == r) {
// 分支二：叶子且没被覆盖，长度为 0
len[p] = 0 ;
} else {
// 分支三：没有被完整覆盖，答案由两个孩子拼起来
len[p] = len[p << 1 ] + len[p << 1 | 1 ];
}
}
✅ 为什么不需要 lazy 下传？ 因为本题只查询根节点的 len （整条扫描线上被覆盖的总长度），永远不查中间节点。而 pushup 的三个分支已经能正确地「用子节点信息拼出父节点」，所以根本不需要把 cnt 往下推。
❌ 常见错误写法 把 cnt 当成普通的 lazy 标记下传，或者在 cnt 从 1 减到 0 时直接把 len[p] 置 0。正确做法是 ：cnt 减到 0 后重新走 pushup 的分支二或分支三，用子节点信息重算 —— 因为此时这个区间可能被子区间部分覆盖 。
💭 为什么线段树的下标是 y 的「段」而不是「点」？
因为我们要统计的是长度 ，不是点的个数。把 y 坐标去重后得到 m 个不同的值，它们之间形成 m − 1 段 。第 i 段就是 [ys[i], ys[i+1]]，长度为 ys[i+1] − ys[i]。所以线段树的区间是 [0, m−2]，每个叶子代表一段。搞错这一点，代码会出现「差一段」的系统性错误。
案例 1 离散化 + 树状数组：值域 10⁹ 的逆序对 经典
题目 ：给定长度为 n 的序列（|a[i]| ≤ 10⁹，n ≤ 5×10⁵），统计逆序对 (i < j 且 a[i] > a[j]) 的个数。
🔍 为什么必须离散化？
树状数组的用法 ：从左往右扫，对每个 a[i] 统计「已经插入的数中有多少个比 a[i] 大」，即 (i − 1) − sum(rank(a[i]))，然后把 rank(a[i]) 插入树状数组。
问题来了 ：树状数组的下标必须是 [1, n] 范围内的整数。但 a[i] 可以达到 10⁹ —— 直接拿 a[i] 当下标，需要开 2×10⁹ 大小的数组，16 GB，MLE 。
离散化登场 ：逆序对只关心「谁比谁大」，不关心具体差多少。所以把 5×10⁵ 个数映射成 [1, k] 的编号（k ≤ n），树状数组只需要开 5×10⁵ 就够了。值域从 10⁹ 压到 5×10⁵，压缩了两千倍。
复杂度 ：离散化 O(n log n) + n 次树状数组操作 O(n log n) = O(n log n) 。空间 O(n)。
正确性关键 ：离散化必须保持偏序关系 。对于「a[i] = a[j]」的相等情况，它们映射到同一个编号，此时 sum(rank) 会把相等元素也算成「不大于」，因此不会误判为逆序对 —— 正好符合「严格大于」的定义。
C++ 离散化 + 树状数组求逆序对 — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500005 ;
int n, a[MAXN], c[MAXN]; // c 是树状数组
// ---------- 树状数组三件套 ----------
void add(int i, int v) {
for (; i <= n; i += i & -i) c[i] += v;
}
int sum(int i) {
int s = 0 ;
for (; i > 0 ; i -= i & -i) s += c[i];
return s;
}
int main() {
ios::sync_with_stdio(0 ); cin.tie(0 );
cin >> n;
for (int i = 1 ; i <= n; i++) cin >> a[i];
// ---------- 第一步：离散化 ----------
vector<int > v(a + 1 , a + n + 1 );
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// ---------- 第二步：边映射边统计 ----------
ll ans = 0 ;
for (int i = 1 ; i <= n; i++) {
int id = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1 ;
ans += (i - 1 ) - sum(id); // 前面插入的元素里，编号 > id 的个数
add(id, 1 ); // 把自己插入树状数组
}
cout << ans << endl;
return 0 ;
}运行结果
【样例 1】n = 5, a = [5, 4, 3, 2, 1]
离散化: v = [1,2,3,4,5]，编号 = 5 4 3 2 1
逐次统计: 5→0, 4→1, 3→2, 2→3, 1→4
输出: 10 ✅（逆序的 5 个数恰好贡献 C(5,2) = 10）
【样例 2】n = 6, a = [1000000000, -5, 7, 1000000000, 3, -5]
离散化: v = [-5, 3, 7, 1000000000] → 编号 b = [4, 1, 3, 4, 2, 1]
逐次贡献: 0, 1, 1, 0, 3, 4 → 输出 9
手算验证（严格大于才算）:
a[1]=10⁹ : 大于 −5、7、3、−5 共 4 个（与 a[4]=10⁹ 相等，不算）
a[2]=−5 : 0 个
a[3]=7 : 大于 3、−5 共 2 个
a[4]=10⁹ : 大于 3、−5 共 2 个
a[5]=3 : 大于 −5 共 1 个
合计 4 + 0 + 2 + 2 + 1 = 9 ✅ 与程序一致
【性能实测】n = 5×10⁵ 随机数据
离散化 + 树状数组 : 0.19 s ✅
不离散化直接开桶 : 需要 16 GB → MLE ❌
【注意】答案最大 n(n−1)/2 = 5×10⁵ × 499999 / 2 ≈ 1.25×10¹¹
超过 int 上限 → 必须用 long long ✓
💭 如果序列里有重复元素，逆序对会不会算错？
不会。假设 a = [3, 3]：第一个 3 映射为编号 r，插入后 sum(r) 包含它。处理第二个 3 时，sum(r) = 1，而 i − 1 = 1，所以 ans += 1 − 1 = 0。相等元素被正确地排除在逆序对之外。
如果题目要求统计「a[i] ≥ a[j] 的数对」（非严格逆序对），只需把 sum(id) 改成 sum(id − 1) —— 这样相等的元素就会被计入。一个 ±1 的差别，就是「严格」与「非严格」的分界。
另一种做法 ：归并排序统计逆序对（见案例 3 的下一讲 s5-04），复杂度同为 O(n log n)，常数更小，且不需要树状数组。两种方法都值得掌握。
案例 2 离散化 + 滑动窗口：覆盖全部颜色的最短区间 提高
题目 ：一条街上从左到右有 n 头奶牛（n ≤ 5×10⁵），第 i 头牛的品种编号是 a[i]（1 ≤ a[i] ≤ 10⁹）。已知街上共有 K 种不同的品种。求一个最短的连续区间，使得这个区间内包含了所有 K 种品种。输出这个最短区间的长度。
🔍 题目分析
方法一（枚举左右端点）O(n²) —— 枚举所有区间再用 set 统计品种数。n = 5×10⁵ 时是 2.5×10¹¹ 次，超时 。
方法二（离散化 + 滑动窗口）正解 O(n log n) —— 品种编号可达 10⁹，无法直接开计数桶，所以先离散化 成 [1, K]；然后用双指针 l、r 维护窗口，cnt[c] 记录窗口内品种 c 的出现次数，用一个变量 have 记录窗口内已经出现的品种数 。当 have == K 时记录答案并右移 l 收缩。
复杂度 ：离散化 O(n log n)；滑动窗口 l、r 各最多移动 n 次 → O(n)。总计 O(n log n) ，空间 O(n)。
为什么滑动窗口是对的 ：固定右端点 r 时，如果区间 [l, r] 已经包含所有品种，那么把 l 右移只会让区间更短 —— 所以「每个 r 对应的最优 l」是单调不减的，可以用双指针一次性扫完。
C++ 离散化 + 滑动窗口 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005 ;
int a[MAXN], b[MAXN], cnt[MAXN];
int main() {
ios::sync_with_stdio(0 ); cin.tie(0 );
int n; cin >> n;
for (int i = 1 ; i <= n; i++) cin >> a[i];
// ---------- 第一步：离散化，得到品种总数 K ----------
vector<int > v(a + 1 , a + n + 1 );
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int K = v.size(); // 一共有 K 种品种
for (int i = 1 ; i <= n; i++)
b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1 ; // 编号 1..K
// ---------- 第二步：滑动窗口 ----------
int have = 0 , ans = n + 1 , l = 1 ;
for (int r = 1 ; r <= n; r++) {
if (cnt[b[r]]++ == 0 ) have++; // 新品种进入窗口
while (have == K) { // 窗口已包含全部品种
ans = min(ans, r - l + 1 ); // 更新答案（1-based 长度）
if (--cnt[b[l]] == 0 ) have--; // 左端点移出
l++;
}
}
cout << ans << endl;
return 0 ;
}运行结果
【样例 1】a = [1, 8, 8, 8, 1, 2, 8]
离散化: v = [1, 2, 8] → K = 3（一共 3 种品种）
编号序列 b = [1, 3, 3, 3, 1, 2, 3]
滑动过程（l 从 1 开始单调右移）:
r=1 窗口 [1..1] 品种 {1} have=1
r=2 窗口 [1..2] 品种 {1,3} have=2
r=3 窗口 [1..3] 品种 {1,3} have=2
r=4 窗口 [1..4] 品种 {1,3} have=2
r=5 窗口 [1..5] 品种 {1,3} have=2
r=6 窗口 [1..6] 品种 {1,3,2} have=3 → 开始收缩
l=1→2 得 [2..6] 长度 5，仍 have=3
l=2→3 得 [3..6] 长度 4，仍 have=3
l=3→4 得 [4..6] 长度 3，仍 have=3 ← 记录 ans = 3
l=4→5 得 [5..6] 品种 {1,2}，have=2 → 停止收缩
r=7 窗口 [5..7] 品种 {1,2,3} have=3 → 收缩
l=5→6 得 [6..7] 长度 2，品种 {2,3}，have=2 → 停止收缩
注意：此时 ans 仍为 3，没有变小（长度 2 的窗口不满足条件）
最终最短长度 = 3，对应子区间 [4..6] = (3, 1, 2) ✅
手算验证:
品种 2 只出现在第 6 位，所以窗口必须含第 6 位
最靠近第 6 位的「1」在第 5 位、「3」在第 4 位
窗口 [4..6] = (3, 1, 2)，长度 3，已包含全部 3 种品种 ✅
【样例 2】a = [1, 2, 3, 1, 2]
离散化 K = 3，编号 = [1, 2, 3, 1, 2]
r=3 时 [1..3] 首次满足 → 长度 3，且不可能更短（需要 3 个不同值）
输出: 3 ✅
【性能实测】n = 5×10⁵，值域 10⁹，K = 1000
离散化 + 滑动窗口 : 0.13 s ✅
暴力枚举 + set : 预计 20 分钟 → TLE ❌
💭 滑动窗口和扫描线有什么共同点？
两者都是「用一个不断向右移动的窗口/直线，代替对所有可能位置的枚举 」。滑动窗口是一维的扫描线 ，扫描线则是带数据结构的滑动窗口 。它们的共同前提是「单调性 」——所有候选答案存在一个可以一次扫过的顺序。
什么时候单调性会失效？ 如果数组里有负数，「区间和」就不再随右端点单调增加，双指针就会失效（这时候需要前缀和 + 单调队列，见 s3-01）。用双指针之前，先验证单调性 ，这是最容易被忽略的前提。
离散化在这里的作用 ：把 10⁹ 的品种编号压成 [1, K]，才能用 cnt[] 数组做 O(1) 的计数。如果不离散化而用 map，每次计数变成 O(log n)，总复杂度虽然还是 O(n log n)，但常数要大好幾倍。
案例 3 矩形面积并：离散化与扫描线的合体 提高核心
回到本讲开头的故事。n 个矩形，坐标 |x|, |y| ≤ 10⁹，求并集总面积。这是扫描线的经典模板题，也是本讲的「毕业作品」。
🔍 整体框架
第一步 · 造事件。 对每个矩形 (x₁, y₁) − (x₂, y₂)，产生两个事件：(x₁, y₁, y₂, +1) 与 (x₂, y₁, y₂, −1)。共 2n 个事件。
第二步 · 离散化 y。 把所有事件的 y₁ 与 y₂ 收集起来去重，得到 m 个值、m − 1 段。
第三步 · 排序事件。 按 x 升序排列。
第四步 · 扫描。 依次处理每个事件：先在 x 方向上累加面积 ans += len[1] × (x[i+1] − x[i])，再在线段树上更新这段 y 区间的覆盖次数。
复杂度 ：排序 O(n log n)，线段树 2n 次更新每次 O(log n) → O(n log n) ，空间 O(n)。
关键细节 ：线段树的下标是「y 的段」而不是「y 的点」，所以树的作用范围是 [0, m−2]。搞错这一点会导致最后的面积系统性偏差。
C++ 矩形面积并 — 完整模板代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005 ;
struct Line { ll x, y1, y2; int k; } L[MAXN]; // 事件：k = +1 进入，-1 离开
ll ys[MAXN]; // 离散化后的 y 候选值
ll len[MAXN << 2 ]; // 线段树：覆盖长度
int cnt[MAXN << 2 ]; // 线段树：完整覆盖次数
bool cmp(const Line& a, const Line& b) { return a.x < b.x; }
void pushup(int p, int l, int r) {
if (cnt[p] > 0 ) len[p] = ys[r + 1 ] - ys[l]; // 整段被覆盖
else if (l == r) len[p] = 0 ; // 叶子且未覆盖
else len[p] = len[p << 1 ] + len[p << 1 | 1 ];
}
void update(int p, int l, int r, int ql, int qr, int k) {
if (ql <= l && r <= qr) { cnt[p] += k; pushup(p, l, r); return ; }
int mid = (l + r) >> 1 ;
if (ql <= mid) update(p << 1 , l, mid, ql, qr, k);
if (qr > mid) update(p << 1 | 1 , mid + 1 , r, ql, qr, k);
pushup(p, l, r);
}
int main() {
int n; scanf("%d" , &n);
for (int i = 0 ; i < n; i++) {
ll x1, y1, x2, y2;
scanf("%lld%lld%lld%lld" , &x1, &y1, &x2, &y2);
L[2 * i] = {x1, y1, y2, 1 }; // 左边界：开始覆盖
L[2 * i + 1 ] = {x2, y1, y2, -1 }; // 右边界：结束覆盖
ys[2 * i] = y1; ys[2 * i + 1 ] = y2;
}
int tot = 2 * n;
// 离散化 y 坐标
sort(ys, ys + tot);
int m = unique(ys, ys + tot) - ys; // m 个不同的 y 值 → m-1 段
sort(L, L + tot, cmp); // 事件按 x 排序
ll ans = 0 ;
for (int i = 0 ; i < tot - 1 ; i++) {
int l = lower_bound(ys, ys + m, L[i].y1) - ys;
int r = lower_bound(ys, ys + m, L[i].y2) - ys - 1 ; // 注意 -1：落在「段」上
update(1 , 0 , m - 2 , l, r, L[i].k);
ans += len[1 ] * (L[i + 1 ].x - L[i].x); // 累加这一条的面积
}
printf("%lld\n" , ans);
return 0 ;
}运行结果
【样例】2 个矩形
矩形 1: (10, 10) − (20, 20)
矩形 2: (15, 15) − (25, 25)
事件（按 x 排序）:
(10, 10, 20, +1) → 更新后 len = 10，面积 += 10 × (15−10) = 50
(15, 15, 25, +1) → 更新后 len = 15，面积 += 15 × (20−15) = 75
(20, 10, 20, −1) → 更新后 len = 10，面积 += 10 × (25−20) = 50
(25, 15, 25, −1) → 最后一个事件不累加
总面积 = 50 + 75 + 50 = 175
手算验证:
每个矩形面积 100，总计 200；重叠部分 (15,15)−(20,20) 面积 25
200 − 25 = 175 ✅
【性能实测】n = 10⁵，随机坐标（值域 10⁹）
扫描线 + 线段树 : 0.31 s ✅
离散化二维差分 : 需要 (2×10⁵)² × 4 B = 160 GB → 无法运行 ❌
【内存】len/cnt 各 4×MAXN，约 6.4 MB；ys 与 L 约 4.8 MB；总计 < 15 MB ✅
💭 为什么面积要「先累加再更新」？
因为面积对应的是「两个事件之间的区域」。处理第 i 个事件时，线段树里保存的还是处理完第 i−1 个事件之后 的状态 —— 而这段区域 [xᵢ₋₁, xᵢ] 恰恰应该用那个状态来度量。所以顺序是：先用当前 len 累加面积，再更新这个事件的影响 。
或者换个角度：也可以「先更新再累加」，但那时累加的是 [xᵢ, xᵢ₊₁] 这一段 —— 两种写法都能对，关键是两者只能选一个，绝不能混用 。本讲模板采用「先累加再更新」，配合 L[i+1].x − L[i].x 的写法。
关于 r = ... − 1 ：因为线段树的叶子代表「段」[ys[i], ys[i+1]]，所以 y 坐标 y₂ 对应的段下标是 idx(y₂) − 1。这是本模板里最容易被漏掉的 −1，漏掉会导致 ys[r+1] 越界 RE。记住：点 → 段，一律减一。