# 离散化（Discretization）

离散化是算法竞赛中极其常用的一种**空间优化与数据预处理**手段。它能够将稀疏、跨度巨大（值域大）的数据集合，在不改变其相互关系的前提下，映射到连续、紧凑的整数下标上。

---

## 1. 什么是离散化

### 1.1 核心思想：保序映射
从数学上看，给定一个包含 $n$ 个元素的集合：
$$S = \{s\_1, s\_2, \dots, s\_n\}$$

离散化是构造一个保序映射函数：
$$f: S \to \{1, 2, \dots, k\}$$
其中 $k$ 是 $S$ 中互不相同的元素个数。该函数 $f$ 必须满足如下核心性质：对于任意的 $s\_i, s\_j \in S$，若：
$$s\_i < s\_j \implies f(s\_i) < f(s\_j)$$

简单来说，离散化就是**在保证相对大小关系不变的前提下，将宽广且稀疏的值域压缩到一段紧凑的、从 1（或 0）开始的连续整数区间**。此过程也常被称为**坐标压缩（Coordinate Compression）**。

---

### 1.2 一个引例：值域压缩
设想这样一个场景：
在无限数轴上分布着一些坐标点。坐标范围极大，例如从 $-10^9$ 到 $10^9$，但坐标点的个数 $n$ 很少，仅有 $10^5$ 个。
若我们想用数组记录坐标 $x$ 上的物品数量：`counts[x] = v`，直接开辟 `int counts[2 * 10^9]` 大小的数组不仅内存无法容纳，更会因为大量未定义区间的空白而造成巨大的空间浪费。

此时，我们发现许多算法（如排序、前缀和、线段树）**仅仅依赖于这些点之间的相对位置关系（序关系），而非它们的绝对物理数值**。
例如，坐标集合 $\{10, 100, 10^9\}$ 与 $\{1, 2, 3\}$ 在偏序关系上完全等价：$10$ 是最小的（映射为 $1$），$100$ 是次小的（映射为 $2$），$10^9$ 是最大的（映射为 $3$）。

经过这层保序映射，我们就可以用大小仅为 $10^5$ 的连续数组进行全部后续维护，内存空间问题迎刃而解。

---

### 1.3 离散化的适用场景
当一个问题满足以下一个或多个特征时，应优先考虑使用离散化：
* **值域巨大，元素稀疏**：涉及的数值（如物理坐标、权值、时间戳）范围极大，而实际用到的点数很少（例如值域 $\le 10^9$，数据量 $\le 10^5$）。
* **只关心相对大小**：算法的正确性完全不依赖于具体数值，仅依赖于它们之间的序关系。
* **需要配合下标敏感的数据结构**：如树状数组、线段树或简单的桶，这些数据结构要求下标必须是连续、小范围的非负整数。

---

## 2. 离散化的标准实现

离散化实现的精髓可以总结为：**“收集 $\to$ 排序 $\to$ 去重 $\to$ 映射”** 四个核心步骤。我们通常借助 C++ 的标准模板库（STL）来实现。

假设待离散化的数据存放在 `std::vector<int> all` 中：

### 2.1 基础实现步骤
1. **收集**：将待处理的值全部收集到向量 `all` 中。
2. **排序**：对 `all` 进行升序排序。
   ```cpp
   sort(all.begin(), all.end());
   ```
3. **去重**：调用 `std::unique` 将相邻的重复元素覆盖并前移，返回逻辑末尾迭代器 `ed`。
   ```cpp
   auto ed = unique(all.begin(), all.end());
   ```
4. **擦除**：通过 `erase` 物理清空尾部的多余脏数据。
   ```cpp
   all.erase(ed, all.end());
   ```

经过上述去重三部曲，`all` 向量即变成了一个有序且无重复元素的映射表。
* 映射关系为：原始值 `all[i]` 对应的离散化值（新索引）即为 `i + 1`（以 1-based 索引为例）。

---

### 2.2 C++ STL unique 函数行为解析
初学者常误认为 `std::unique` 会自动改变容器的物理大小，实则不然。
其真实工作机制为：将所有非重复元素搬运移动至容器头部，覆盖掉重复的数据，并返回一个指向新去重区间逻辑终点（即最后一个有效元素之后的位置）的迭代器。

例如，对于 `vector` 容器：
```text
初始状态：        {1, 5, 1, 3, 5, 2}
1. sort 后：     {1, 1, 2, 3, 5, 5}
2. unique 后：   {1, 2, 3, 5, ?, ?} 
                  (其中 ? 代表脏数据，unique 返回指向第一个 ? 处的迭代器)
3. erase 后：    {1, 2, 3, 5}
```

---

### 2.3 查找映射：lower_bound
在构建好保序映射表 `all` 后，如果需要查询原数值 $x$ 的离散化 ID，可在对数时间 $O(\log n)$ 内使用二分查找（`lower_bound`）获取位置：

```cpp
// 假设 all 是排好序且已经去重的保序映射表
int get_id(int x) {
    // 0-based 索引返回为：lower_bound(all.begin(), all.end(), x) - all.begin();
    // 下面转换为 1-based 索引返回，更加适合树状数组等结构
    return lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}
```

---

### 2.4 C++ 完整模板代码
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> all; // 存储所有待离散化的原始值

// 获取原始值 x 离散化后的新 ID (1-based)
int getId(int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}

// 离散化去重三部曲
void discretize() {
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// 1. 收集值
    all.push_back(100);
    all.push_back(20);
    all.push_back(100);
    all.push_back(50);

// 2. 离散化
    discretize(); // all 向量变为：{20, 50, 100}

// 3. 映射查询
    cout << "20 的离散值: " << getId(20) << endl;   // 输出 1
    cout << "50 的离散值: " << getId(50) << endl;   // 输出 2
    cout << "100 的离散值: " << getId(100) << endl; // 输出 3
    cout << "离散值 1 对应的原值: " << all[getId(20) - 1] << endl; // 输出 20

return 0;
}
```

---

### 2.5 复杂度分析
设原始待离散化的数据量大小为 $N$。
* **时间复杂度**：
  * 排序阶段：$O(N \log N)$
  * 去重阶段：$O(N)$
  * 查询映射：单次查询 $O(\log K)$（其中 $K$ 为不同元素的个数，$K \le N$）。
  * 预处理阶段总时间复杂度由排序主导，为 **$O(N \log N)$**。
* **空间复杂度**：需要开辟一个长度与 $N$ 正相关的向量存储去重前的中间元素，为 **$O(N)$**。

---

## 3. 基础应用与经典例题

### 3.1 坐标压缩与并查集
当问题涉及对元素“相等、不相等”等关系判定，且元素取值空间极大时，离散化常配合并查集（Disjoint Set Union, DSU）联袂登场。

#### 例题 1：洛谷 P1955 [NOI2015] 程序自动分析
* **题意概括**：
  给定 $n$ 条约束，格式为 `i j e`（变量 $x\_i$ 和 $x\_j$）。
  若 $e = 1$，代表 $x\_i = x\_j$；若 $e = 0$，代表 $x\_i \ne x\_j$。
  问这些约束是否存在内部冲突与矛盾。变量下标 $i, j \le 10^9$。

* **解题思路**：
  1. **等价传递性**：相等关系具有天然的传递性，适合用并查集进行连通支合并。
  2. **离线处理**：相等关系是不相等判定的前提。因此我们需要“先离线分类”，把所有 $e=1$ 的相等约束处理完毕、完成合并后，再去逐条判断 $e=0$ 的不相等约束。若不相等两端的变量在并查集中代表同一个集合（根相同），即代表冲突。
  3. **离散化解围**：下标 $i, j \le 10^9$，并查集数组无法开辟如此大规模。通过收集所有出现过的下标，排序去重离散化为 $[1, K]$ 的紧凑索引，再对其建并查集即可。

#### C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200005; // 约束数量最多 10^5，涉及坐标数最大 2*10^5

struct Constraint {
    int i, j, e;
} q[N];

vector<int> all; // 离散化映射表
int p[N * 2];    // 并查集数组

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int getId(int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}

void solve() {
    int n;
    cin >> n;

all.clear();
    vector<pair<int, int>> neq; // 专门存储不等式关系

for (int i = 0; i < n; ++i) {
        int u, v, e;
        cin >> u >> v >> e;
        q[i] = {u, v, e};
        all.push_back(u);
        all.push_back(v);
    }

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

int k = all.size();
    for (int i = 1; i <= k; ++i) p[i] = i; // 初始化并查集

// 第一步：优先合并所有 e == 1 的相等变量
    for (int i = 0; i < n; ++i) {
        if (q[i].e == 1) {
            int u = getId(q[i].i);
            int v = getId(q[i].j);
            p[find(u)] = find(v);
        } else {
            neq.push_back({q[i].i, q[i].j});
        }
    }

// 第二步：检验不等约束是否发生连通性矛盾
    bool ok = true;
    for (auto& pa : neq) {
        int u = getId(pa.first);
        int v = getId(pa.second);
        if (find(u) == find(v)) {
            ok = false;
            break;
        }
    }

if (ok) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}
```

---

### 3.2 坐标压缩与树状数组
在数轴上进行**单点修改**与**区间求和查询**时，若坐标数值极大，离散化是启用树状数组的前置必要条件。

#### 例题 2：洛谷 P2068 统计和
* **题意概括**：
  给定名义长度可达 $10^9$ 的全 0 数组，进行 $M$ 次操作：
  1) `x v`：将位置 $x$ 的值增加 $v$。
  2) `y l r`（表示为求和）：查询区间 $[l, r]$ 内所有数的和。操作总数 $M \le 2 \times 10^5$。

* **核心分析**：
  由于 $l, r$ 等坐标很大，我们需要对其离散化。
  **关键细节**：不仅单点修改的坐标 $x$ 应该加入离散化集合，**区间查询的端点 $l$ 和 $r$ 也必须无一遗漏地加入待离散化的映射表中**。因为查询区间和 `sum(l, r)` 需要通过 `prefix_sum(r) - prefix_sum(l - 1)` 实现，我们必须知道 $l$ 和 $r$（包括 $l-1$）在离散映射后坐标系中的准确对应关系，否则由于漏项会导致 lower_bound 无法精确匹配。

#### C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 300005; // 坐标点数量最多 M * 2

struct Query {
    char t;
    int x, y;
} q[N];

int a[N], ac; // 离散坐标收集器
long long tr[N];
int k;        // 离散去重后的总长度

int gid(int x) {
    return lower_bound(a, a + k, x) - a + 1;
}

void add(int p, int v) {
    for (; p <= k; p += p & -p) tr[p] += v;
}

long long qry(int p) {
    long long res = 0;
    for (; p > 0; p -= p & -p) res += tr[p];
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n, m;
    if (!(cin >> n >> m)) return 0;

for (int i = 0; i < m; ++i) {
        char t; int x, y;
        cin >> t >> x >> y;
        q[i] = {t, x, y};
        a[ac++] = x;
        a[ac++] = y; // 端点全部纳入离散数组
    }

sort(a, a + ac);
    k = unique(a, a + ac) - a; // 去重后得到新坐标系的大小 k

for (int i = 0; i < m; ++i) {
        if (q[i].t == 'x') {
            int p = gid(q[i].x);
            add(p, q[i].y);
        } else {
            int l = gid(q[i].x);
            int r = gid(q[i].y);
            cout << qry(r) - qry(l - 1) << "\n";
        }
    }

return 0;
}
```

---

## 4. 进阶技巧：区间离散化

在许多问题中，我们的操作对象并非独立的点，而是**连续的区间（线段）**（如区间染色问题、矩形面积并等）。

### 4.1 核心思想
点离散化关注孤立点，而区间离散化关注**端点分割出的基本单元区间（元区间）**。
设所有区间端点经排序去重后为 $p\_1, p\_2, \dots, p\_m$。它们将数轴自然分割成了以下两种物理单元：
* **单点单元**：$p\_1, p\_2, \dots, p\_m$
* **开区间单元**：$(p\_1, p\_2), (p\_2, p\_3), \dots, (p\_{m-1}, p\_m)$

原始坐标中的任意操作闭区间 $[L\_i, R\_i]$，都可以被表达为这些基本点单元与开区间单元的并集。

---

### 4.2 处理闭区间的经典技巧：$r + 1$
为了便于利用线段树等工具来处理一维连续闭区间的修改，我们常用一个经典方法：
如果操作对象是连续的闭区间 $[l, r]$，我们在收集端点时，**将 $l$ 与 $r + 1$ 共同加入待离散化的映射集合**。

这样，排序去重后的点集 $p\_1, p\_2, \dots, p\_m$ 构成了 $m - 1$ 个**左闭右开**的基本区间：
$$[p\_i, p\_{i+1}) \quad (\text{for } 1 \le i < m)$$

由于基本区间之间是无缝首尾拼接的，原区间 $[l, r]$（物理意义等价于左闭右开的 $[l, r+1)$）将直接一一对应离散化后从 $\text{getId}(l)$ 到 $\text{getId}(r+1) - 1$ 的这一连串整数下标：

#### 实妙演示：
在 $[10, 20]$ 与 $[15, 30]$ 进行区间染色。
1. **收集端点**：收集 $l$ 与 $r + 1 \to \{10, 21, 15, 31\}$。
2. **排序去重**：映射表为 `all = {10, 15, 21, 31}`。
3. **划分基本区间（元区间）**：
   * 基本区间 1：$[10, 15)$
   * 基本区间 2：$[15, 21)$
   * 基本区间 3：$[21, 31)$
4. **原区间映射**：
   * 原区间 $[10, 20]$ 等价于 $[10, 21)$。其覆盖了基本区间 1、2。映射到离散新坐标系中为新区间：
     $$[\text{getId}(10), \text{getId}(21) - 1] = [1, 3 - 1] = [1, 2]$$
   * 原区间 $[15, 30]$ 等价于 $[15, 31)$。其覆盖了基本区间 2、3。映射到离散新坐标系中为：
     $$[\text{getId}(15), \text{getId}(31) - 1] = [2, 4 - 1] = [2, 3]$$

这正是我们能用线段树解决区间染色、扫描线等计算几何问题的空间数学根基。

---

## 5. 扫描线与区间离散化

### 5.1 矩形面积并（洛谷 P5490 【模板】扫描线）
#### 核心机制
使用垂直扫描线从左向右扫过平面，将面积并问题分割为一系列窄矩形条带。事件点为每个矩形的左边界（入边，权值 $+1$）和右边界（出边，权值 $-1$）。我们利用一维线段树来动态维护扫描线上 $y$ 轴方向被覆盖的有效总长度 $len$。

```
     +--------+ 
     |        | 
-----|--------|-----> 扫描线
     +--------+
     x1       x2
```

由于 $y$ 的坐标取值极其稀疏且大，必须对其进行**区间离散化**。
设去重后的 $y$ 坐标集合为 $Y\_1, Y\_2, \dots, Y\_m$，共有 $m - 1$ 个左闭右开的基本区间 $[Y\_i, Y\_{i+1})$。我们建一棵包含 $m - 1$ 个叶子节点的线段树进行维护。

#### C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;

struct Edge {
    long long x, y1, y2;
    int k; // 1 为入边，-1 为出边
    bool operator<(const Edge& o) const {
        return x < o.x;
    }
};

struct Node {
    int cnt;        // 覆盖次数
    long long len;  // 被完全覆盖的物理长度
} tr[N * 8];        // 2*N 个事件，y 坐标对应 2*N，线段树大小开 8 倍

vector<Edge> segs;
vector<long long> all_y;

int find(long long y) {
    return lower_bound(all_y.begin(), all_y.end(), y) - all_y.begin();
}

void pushup(int u, int l, int r) {
    if (tr[u].cnt > 0) { // 如果当前节点所代表的区间被完全覆盖
        tr[u].len = all_y[r + 1] - all_y[l];
    } else if (l == r) { // 叶子节点且未被覆盖
        tr[u].len = 0;
    } else {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
}

void build(int u, int l, int r) {
    tr[u] = {0, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void upd(int u, int l, int r, int ql, int qr, int k) {
    if (ql <= l && r <= qr) {
        tr[u].cnt += k;
    } else {
        int mid = (l + r) >> 1;
        if (ql <= mid) upd(u << 1, l, mid, ql, qr, k);
        if (qr > mid) upd(u << 1 | 1, mid + 1, r, ql, qr, k);
    }
    pushup(u, l, r);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segs.push_back({x1, y1, y2, 1});
        segs.push_back({x2, y1, y2, -1});
        all_y.push_back(y1);
        all_y.push_back(y2);
    }

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

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

int m = all_y.size();
    build(1, 0, m - 2); // m 个端点有 m-1 个基本区间，索引为 0 到 m-2

long long ans = 0;
    for (size_t i = 0; i < segs.size() - 1; ++i) {
        int y1_idx = find(segs[i].y1);
        int y2_idx = find(segs[i].y2);
        if (y1_idx < y2_idx) {
            upd(1, 0, m - 2, y1_idx, y2_idx - 1, segs[i].k);
        }
        ans += tr[1].len * (segs[i + 1].x - segs[i].x);
    }

cout << ans << endl;
    return 0;
}
```

---

### 5.2 矩形周长并（洛谷 P1856 Picture）
周长并比面积并更为复杂，需要利用**正交分解**。将周长分别投影、分解为水平周长和垂直周长：
1. **水平周长**：在扫描线宽度移动时，当前状态下存在的独立的不相交覆盖线段段数为 $sc$。每段在上下边界均对周长有贡献。水平贡献为：
   $$\text{Horizontal\_Len} = 2 \times tr[1].sc \times (x\_{i+1} - x\_i)$$
2. **垂直周长**：每步扫描线更新前后有效 $y$ 覆盖长度的绝对差值 $|len\_{\text{after}} - len\_{\text{before}}|$，正好对应本次新产生（或消逝）的垂直边。

为此，线段树除了维护覆盖层数 `cnt` 和总长 `len`，还需要维护：
* `sc`：节点区间内不相交的连续覆盖段数量。
* `lv, rv`：节点区间的左右端点是否已被覆盖。

#### 核心 Pushup 段合并逻辑
对左右子节点进行区间合并时，我们需要通过左右端点连通状态来动态更新 $sc$：
$$tr[u].sc = tr[ls].sc + tr[rs].sc - (tr[ls].rv \land tr[rs].lv)$$

#### C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 5005;
const int XE = MAXN * 2;
const int XT = XE * 4;

struct Event {
    int x;
    int y1, y2;
    int t; // 1 为左边界，-1 为右边界
    bool operator<(const Event& o) const {
        if (x != o.x) return x < o.x;
        return t > o.t; // 相同坐标，左边界优先
    }
};

struct Node {
    int cnt;
    long long len;
    int sc; // 不相交的连续段数
    bool lv, rv;
} tr[XT];

Event e[XE];
vector<int> ys;

int fid(int val) {
    return lower_bound(ys.begin(), ys.end(), val) - ys.begin();
}

#define ls (u << 1)
#define rs (u << 1 | 1)

void pu(int u, int L, int R) {
    if (tr[u].cnt > 0) {
        tr[u].len = ys[R + 1] - ys[L];
        tr[u].sc = 1;
        tr[u].lv = tr[u].rv = true;
    } else if (L == R) {
        tr[u].len = 0;
        tr[u].sc = 0;
        tr[u].lv = tr[u].rv = false;
    } else {
        tr[u].len = tr[ls].len + tr[rs].len;
        tr[u].lv = tr[ls].lv;
        tr[u].rv = tr[rs].rv;
        tr[u].sc = tr[ls].sc + tr[rs].sc;
        if (tr[ls].rv && tr[rs].lv) {
            tr[u].sc--; // 左右接触点均覆盖，则合并连续段
        }
    }
}

void ud(int u, int L, int R, int qL, int qR, int v) {
    if (qL <= L && R <= qR) {
        tr[u].cnt += v;
        pu(u, L, R);
        return;
    }
    int M = L + (R - L) / 2;
    if (qL <= M) ud(ls, L, M, qL, qR, v);
    if (qR > M)  ud(rs, M + 1, R, qL, qR, v);
    pu(u, L, R);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n;
    if (!(cin >> n)) return 0;

int ec = 0;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        e[ec++] = {x1, y1, y2, 1};
        e[ec++] = {x2, y1, y2, -1};
        ys.push_back(y1);
        ys.push_back(y2);
    }

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

sort(e, e + ec);

long long ans = 0;
    long long lln = 0; // 上次总有效 y 轴覆盖长度
    int my = ys.size();

for (int i = 0; i < ec; ++i) {
        if (i > 0) {
            // 累加水平周长
            ans += tr[1].sc * 2LL * (e[i].x - e[i - 1].x);
        }

int y1x = fid(e[i].y1);
        int y2x = fid(e[i].y2);

if (y1x < y2x) {
            ud(1, 0, my - 2, y1x, y2x - 1, e[i].t);
        }

// 累加垂直周长
        ans += abs(tr[1].len - lln);
        lln = tr[1].len;
    }

cout << ans << endl;
    return 0;
}
```

---

## 6. 进阶联系与拓展

### 6.1 CDQ 分治与三维偏序（洛谷 P3810）
三维偏序是 CDQ 分治的核心应用场景：对含有元素 $(a\_i, b\_i, c\_i)$ 的偏序对计数。
1. 第一维 $a$ 排序去重。
2. 第二维 $b$ 使用 CDQ 双指针分治归并。
3. 第三维 $c$ 借由树状数组维护。
由于 $c$ 的数值空间很大，在归并过程中插入树状数组前，必须对其进行坐标离散化。

---

### 6.2 离线处理与树状数组（洛谷 P1972 HH的项链）
* **题意**：求区间 $[l, r]$ 内有多少个互不相同的数。
* **离线思路**：将所有查询根据右端点 $r$ 升序排序。
* **双指针树状数组维护**：从左向右扫描，每当遇到数值 `a[i]`，若之前出现过，从之前位置注销（`add(prev_pos, -1)`），并在当前位置增加贡献（`add(i, 1)`）。这样可以保证树状数组中只记录每个数值“最后一次出现”的位置。
* **离散化必要性**：如果数值本身可达 $10^9$，则我们需要在离线前对其全部离散化，这样记录原数值上一次出现的 `pos[a[i]]` 辅助位置数组便能以 $O(1)$ 的小空间高效寻址。

---

## 7. 常见陷阱与避坑指南

### 7.1 如何判断需要离散化？
* **值域大而点稀疏**：坐标数值远大于实际元素个数时（如坐标 $10^9$，但元素个数只有 $10^5$），几乎必然需要离散化。
* **只看序不看数值**：只要判定偏序（如 $>$、$<$)，或等价传递（如 $=$、$\ne$)，不依赖绝对相减或加法量级时，离散化是安全的。
* **下标约束**：计划使用的树状数组/线段树受制于大值域而无法开辟数组时。

### 7.2 去重与索引对齐
* **unique 盲区**：`std::unique` 并没有从物理上裁剪 vector 空间，它仅执行覆盖前移。**去重必须紧跟 `erase`。**
* **1-based vs 0-based 对齐**：`std::lower_bound` 相比起点 `begin()` 的偏移量从 `0` 开始。而树状数组通常不接收索引 `0`。此时在 `getId()` 中需要统一进行 `+1` 操作。
* **漏项离散化**：如果离散化不完全（例如：只对原始数据进行了映射，而忘记把区间查询的 $l, r$ 端点一同扔进 `all` 中，极易导致 lower_bound 无法精确匹配或返回未定义的乱序，引发底层断言故障）。

---

## 8. 经典例题选讲

### 例题 A：洛谷 P3740 [HAOI2014] 贴海报 (区间离散化)
* **思路**：
  将长度可达 $10^7$ 的板上，贴 $m \le 1000$ 张海报。
  区间覆盖求最终可见海报数。
  我们将端点 $l\_i$ 与 $r\_i + 1$ 收集起来进行区间左闭右开离散化，通过线段树倒序覆盖并查询非零区间来统计可见张数。

#### C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXM = 1005;

struct Poster {
    int l, r;
};

struct Seg {
    int s;  // 未被覆盖的基本区间个数
    bool t; // 懒标记
};

int n, m;
Poster p[MAXM];
vector<int> d; // 区间离散化
Seg tr[MAXM * 8];

void psh(int u, int l, int r) {
    if (tr[u].t) {
        tr[u << 1].t = tr[u << 1 | 1].t = true;
        tr[u << 1].s = tr[u << 1 | 1].s = 0;
        tr[u].t = false;
    }
}

void bld(int u, int l, int r) {
    tr[u].t = false;
    if (l == r) {
        tr[u].s = 1;
        return;
    }
    int mid = (l + r) >> 1;
    bld(u << 1, l, mid);
    bld(u << 1 | 1, mid + 1, r);
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

void upd(int u, int l, int r, int ql, int qr) {
    if (tr[u].s == 0) return;
    if (ql <= l && r <= qr) {
        tr[u].s = 0;
        tr[u].t = true;
        return;
    }
    psh(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) upd(u << 1, l, mid, ql, qr);
    if (qr > mid)  upd(u << 1 | 1, mid + 1, r, ql, qr);
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

int ask(int u, int l, int r, int ql, int qr) {
    if (tr[u].s == 0) return 0;
    if (ql <= l && r <= qr) return tr[u].s;
    psh(u, l, r);
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res += ask(u << 1, l, mid, ql, qr);
    if (qr > mid)  res += ask(u << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        cin >> p[i].l >> p[i].r;
        d.push_back(p[i].l);
        d.push_back(p[i].r + 1); // 左闭右开区间处理
    }

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

int tot = d.size();
    bld(1, 1, tot - 1);

int ans = 0;
    for (int i = m; i >= 1; --i) {
        int l = lower_bound(d.begin(), d.end(), p[i].l) - d.begin() + 1;
        int r = lower_bound(d.begin(), d.end(), p[i].r + 1) - d.begin();

if (ask(1, 1, tot - 1, l, r) > 0) {
            ans++;
        }
        upd(1, 1, tot - 1, l, r);
    }

cout << ans << endl;
    return 0;
}
```

---

## 9. 推荐刷题列表

离散化（Discretization）

离散化是算法竞赛中极其常用的一种空间优化与数据预处理手段。它能够将稀疏、跨度巨大（值域大）的数据集合，在不改变其相互关系的前提下，映射到连续、紧凑的整数下标上。

1. 什么是离散化

1.1 核心思想：保序映射

从数学上看，给定一个包含 $n$ 个元素的集合： $$S = {s_1, s_2, \dots, s_n}$$

离散化是构造一个保序映射函数： $$f: S \to {1, 2, \dots, k}$$ 其中 $k$ 是 $S$ 中互不相同的元素个数。该函数 $f$ 必须满足如下核心性质：对于任意的 $s_i, s_j \in S$，若： $$s_i < s_j \implies f(s_i) < f(s_j)$$

简单来说，离散化就是在保证相对大小关系不变的前提下，将宽广且稀疏的值域压缩到一段紧凑的、从 1（或 0）开始的连续整数区间。此过程也常被称为坐标压缩（Coordinate Compression）。

1.2 一个引例：值域压缩

设想这样一个场景：在无限数轴上分布着一些坐标点。坐标范围极大，例如从 $-10^9$ 到 $10^9$，但坐标点的个数 $n$ 很少，仅有 $10^5$ 个。若我们想用数组记录坐标 $x$ 上的物品数量：counts[x] = v，直接开辟 int counts[2 * 10^9] 大小的数组不仅内存无法容纳，更会因为大量未定义区间的空白而造成巨大的空间浪费。

此时，我们发现许多算法（如排序、前缀和、线段树）仅仅依赖于这些点之间的相对位置关系（序关系），而非它们的绝对物理数值。例如，坐标集合 ${10, 100, 10^9}$ 与 ${1, 2, 3}$ 在偏序关系上完全等价：$10$ 是最小的（映射为 $1$），$100$ 是次小的（映射为 $2$），$10^9$ 是最大的（映射为 $3$）。

经过这层保序映射，我们就可以用大小仅为 $10^5$ 的连续数组进行全部后续维护，内存空间问题迎刃而解。

1.3 离散化的适用场景

当一个问题满足以下一个或多个特征时，应优先考虑使用离散化： * 值域巨大，元素稀疏：涉及的数值（如物理坐标、权值、时间戳）范围极大，而实际用到的点数很少（例如值域 $\le 10^9$，数据量 $\le 10^5$）。 * 只关心相对大小：算法的正确性完全不依赖于具体数值，仅依赖于它们之间的序关系。 * 需要配合下标敏感的数据结构：如树状数组、线段树或简单的桶，这些数据结构要求下标必须是连续、小范围的非负整数。

2. 离散化的标准实现

离散化实现的精髓可以总结为：“收集 $\to$ 排序 $\to$ 去重 $\to$ 映射” 四个核心步骤。我们通常借助 C++ 的标准模板库（STL）来实现。

假设待离散化的数据存放在 std::vector<int> all 中：

2.1 基础实现步骤

收集：将待处理的值全部收集到向量 all 中。
排序：对 all 进行升序排序。 cpp sort(all.begin(), all.end());
去重：调用 std::unique 将相邻的重复元素覆盖并前移，返回逻辑末尾迭代器 ed。 cpp auto ed = unique(all.begin(), all.end());
擦除：通过 erase 物理清空尾部的多余脏数据。 cpp all.erase(ed, all.end());

经过上述去重三部曲，all 向量即变成了一个有序且无重复元素的映射表。 * 映射关系为：原始值 all[i] 对应的离散化值（新索引）即为 i + 1（以 1-based 索引为例）。

2.2 C++ STL unique 函数行为解析

初学者常误认为 std::unique 会自动改变容器的物理大小，实则不然。其真实工作机制为：将所有非重复元素搬运移动至容器头部，覆盖掉重复的数据，并返回一个指向新去重区间逻辑终点（即最后一个有效元素之后的位置）的迭代器。

例如，对于 vector 容器：

初始状态：        {1, 5, 1, 3, 5, 2}
1. sort 后：     {1, 1, 2, 3, 5, 5}
2. unique 后：   {1, 2, 3, 5, ?, ?} 
                  (其中 ? 代表脏数据，unique 返回指向第一个 ? 处的迭代器)
3. erase 后：    {1, 2, 3, 5}

2.3 查找映射：lower_bound

在构建好保序映射表 all 后，如果需要查询原数值 $x$ 的离散化 ID，可在对数时间 $O(\log n)$ 内使用二分查找（lower_bound）获取位置：

// 假设 all 是排好序且已经去重的保序映射表
int get_id(int x) {
    // 0-based 索引返回为：lower_bound(all.begin(), all.end(), x) - all.begin();
    // 下面转换为 1-based 索引返回，更加适合树状数组等结构
    return lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}

2.4 C++ 完整模板代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> all; // 存储所有待离散化的原始值

// 获取原始值 x 离散化后的新 ID (1-based)
int getId(int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}

// 离散化去重三部曲
void discretize() {
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // 1. 收集值
    all.push_back(100);
    all.push_back(20);
    all.push_back(100);
    all.push_back(50);

    // 2. 离散化
    discretize(); // all 向量变为：{20, 50, 100}

    // 3. 映射查询
    cout << "20 的离散值: " << getId(20) << endl;   // 输出 1
    cout << "50 的离散值: " << getId(50) << endl;   // 输出 2
    cout << "100 的离散值: " << getId(100) << endl; // 输出 3
    cout << "离散值 1 对应的原值: " << all[getId(20) - 1] << endl; // 输出 20

    return 0;
}

2.5 复杂度分析

设原始待离散化的数据量大小为 $N$。 * 时间复杂度： * 排序阶段：$O(N \log N)$ * 去重阶段：$O(N)$ * 查询映射：单次查询 $O(\log K)$（其中 $K$ 为不同元素的个数，$K \le N$）。 * 预处理阶段总时间复杂度由排序主导，为 $O(N \log N)$。 * 空间复杂度：需要开辟一个长度与 $N$ 正相关的向量存储去重前的中间元素，为 $O(N)$。

3. 基础应用与经典例题

3.1 坐标压缩与并查集

当问题涉及对元素“相等、不相等”等关系判定，且元素取值空间极大时，离散化常配合并查集（Disjoint Set Union, DSU）联袂登场。

例题 1：洛谷 P1955 [NOI2015] 程序自动分析

题意概括：给定 $n$ 条约束，格式为 i j e（变量 $x_i$ 和 $x_j$）。若 $e = 1$，代表 $x_i = x_j$；若 $e = 0$，代表 $x_i \ne x_j$。问这些约束是否存在内部冲突与矛盾。变量下标 $i, j \le 10^9$。
解题思路：
等价传递性：相等关系具有天然的传递性，适合用并查集进行连通支合并。
离线处理：相等关系是不相等判定的前提。因此我们需要“先离线分类”，把所有 $e=1$ 的相等约束处理完毕、完成合并后，再去逐条判断 $e=0$ 的不相等约束。若不相等两端的变量在并查集中代表同一个集合（根相同），即代表冲突。
离散化解围：下标 $i, j \le 10^9$，并查集数组无法开辟如此大规模。通过收集所有出现过的下标，排序去重离散化为 $[1, K]$ 的紧凑索引，再对其建并查集即可。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200005; // 约束数量最多 10^5，涉及坐标数最大 2*10^5

struct Constraint {
    int i, j, e;
} q[N];

vector<int> all; // 离散化映射表
int p[N * 2];    // 并查集数组

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int getId(int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}

void solve() {
    int n;
    cin >> n;

    all.clear();
    vector<pair<int, int>> neq; // 专门存储不等式关系

    for (int i = 0; i < n; ++i) {
        int u, v, e;
        cin >> u >> v >> e;
        q[i] = {u, v, e};
        all.push_back(u);
        all.push_back(v);
    }

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

    int k = all.size();
    for (int i = 1; i <= k; ++i) p[i] = i; // 初始化并查集

    // 第一步：优先合并所有 e == 1 的相等变量
    for (int i = 0; i < n; ++i) {
        if (q[i].e == 1) {
            int u = getId(q[i].i);
            int v = getId(q[i].j);
            p[find(u)] = find(v);
        } else {
            neq.push_back({q[i].i, q[i].j});
        }
    }

    // 第二步：检验不等约束是否发生连通性矛盾
    bool ok = true;
    for (auto& pa : neq) {
        int u = getId(pa.first);
        int v = getId(pa.second);
        if (find(u) == find(v)) {
            ok = false;
            break;
        }
    }

    if (ok) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

3.2 坐标压缩与树状数组

在数轴上进行单点修改与区间求和查询时，若坐标数值极大，离散化是启用树状数组的前置必要条件。

例题 2：洛谷 P2068 统计和

题意概括：给定名义长度可达 $10^9$ 的全 0 数组，进行 $M$ 次操作： 1) x v：将位置 $x$ 的值增加 $v$。 2) y l r（表示为求和）：查询区间 $[l, r]$ 内所有数的和。操作总数 $M \le 2 \times 10^5$。
核心分析：由于 $l, r$ 等坐标很大，我们需要对其离散化。 关键细节：不仅单点修改的坐标 $x$ 应该加入离散化集合，区间查询的端点 $l$ 和 $r$ 也必须无一遗漏地加入待离散化的映射表中。因为查询区间和 sum(l, r) 需要通过 prefix_sum(r) - prefix_sum(l - 1) 实现，我们必须知道 $l$ 和 $r$（包括 $l-1$）在离散映射后坐标系中的准确对应关系，否则由于漏项会导致 lower_bound 无法精确匹配。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 300005; // 坐标点数量最多 M * 2 

struct Query {
    char t;
    int x, y;
} q[N];

int a[N], ac; // 离散坐标收集器
long long tr[N];
int k;        // 离散去重后的总长度

int gid(int x) {
    return lower_bound(a, a + k, x) - a + 1;
}

void add(int p, int v) {
    for (; p <= k; p += p & -p) tr[p] += v;
}

long long qry(int p) {
    long long res = 0;
    for (; p > 0; p -= p & -p) res += tr[p];
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        char t; int x, y;
        cin >> t >> x >> y;
        q[i] = {t, x, y};
        a[ac++] = x;
        a[ac++] = y; // 端点全部纳入离散数组
    }

    sort(a, a + ac);
    k = unique(a, a + ac) - a; // 去重后得到新坐标系的大小 k

    for (int i = 0; i < m; ++i) {
        if (q[i].t == 'x') {
            int p = gid(q[i].x);
            add(p, q[i].y);
        } else {
            int l = gid(q[i].x);
            int r = gid(q[i].y);
            cout << qry(r) - qry(l - 1) << "\n";
        }
    }

    return 0;
}

4. 进阶技巧：区间离散化

在许多问题中，我们的操作对象并非独立的点，而是连续的区间（线段）（如区间染色问题、矩形面积并等）。

4.1 核心思想

点离散化关注孤立点，而区间离散化关注端点分割出的基本单元区间（元区间）。设所有区间端点经排序去重后为 $p_1, p_2, \dots, p_m$。它们将数轴自然分割成了以下两种物理单元： * 单点单元：$p_1, p_2, \dots, p_m$ * 开区间单元：$(p_1, p_2), (p_2, p_3), \dots, (p_{m-1}, p_m)$

原始坐标中的任意操作闭区间 $[L_i, R_i]$，都可以被表达为这些基本点单元与开区间单元的并集。

4.2 处理闭区间的经典技巧：$r + 1$

为了便于利用线段树等工具来处理一维连续闭区间的修改，我们常用一个经典方法：如果操作对象是连续的闭区间 $[l, r]$，我们在收集端点时，将 $l$ 与 $r + 1$ 共同加入待离散化的映射集合。

这样，排序去重后的点集 $p_1, p_2, \dots, p_m$ 构成了 $m - 1$ 个左闭右开的基本区间： $$[p_i, p_{i+1}) \quad (\text{for } 1 \le i < m)$$

实妙演示：

在 $[10, 20]$ 与 $[15, 30]$ 进行区间染色。 1. 收集端点：收集 $l$ 与 $r + 1 \to {10, 21, 15, 31}$。 2. 排序去重：映射表为 all = {10, 15, 21, 31}。 3. 划分基本区间（元区间）： * 基本区间 1：$[10, 15)$ * 基本区间 2：$[15, 21)$ * 基本区间 3：$[21, 31)$ 4. 原区间映射： * 原区间 $[10, 20]$ 等价于 $[10, 21)$。其覆盖了基本区间 1、2。映射到离散新坐标系中为新区间： $$[\text{getId}(10), \text{getId}(21) - 1] = [1, 3 - 1] = [1, 2]$$ * 原区间 $[15, 30]$ 等价于 $[15, 31)$。其覆盖了基本区间 2、3。映射到离散新坐标系中为： $$[\text{getId}(15), \text{getId}(31) - 1] = [2, 4 - 1] = [2, 3]$$

这正是我们能用线段树解决区间染色、扫描线等计算几何问题的空间数学根基。

5. 扫描线与区间离散化

5.1 矩形面积并（洛谷 P5490 【模板】扫描线）

核心机制

使用垂直扫描线从左向右扫过平面，将面积并问题分割为一系列窄矩形条带。事件点为每个矩形的左边界（入边，权值 $+1$）和右边界（出边，权值 $-1$）。我们利用一维线段树来动态维护扫描线上 $y$ 轴方向被覆盖的有效总长度 $len$。

     +--------+ 
     |        | 
-----|--------|-----> 扫描线
     +--------+
     x1       x2

由于 $y$ 的坐标取值极其稀疏且大，必须对其进行区间离散化。设去重后的 $y$ 坐标集合为 $Y_1, Y_2, \dots, Y_m$，共有 $m - 1$ 个左闭右开的基本区间 $[Y_i, Y_{i+1})$。我们建一棵包含 $m - 1$ 个叶子节点的线段树进行维护。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;

struct Edge {
    long long x, y1, y2;
    int k; // 1 为入边，-1 为出边
    bool operator<(const Edge& o) const {
        return x < o.x;
    }
};

struct Node {
    int cnt;        // 覆盖次数
    long long len;  // 被完全覆盖的物理长度
} tr[N * 8];        // 2*N 个事件，y 坐标对应 2*N，线段树大小开 8 倍

vector<Edge> segs;
vector<long long> all_y;

int find(long long y) {
    return lower_bound(all_y.begin(), all_y.end(), y) - all_y.begin();
}

void pushup(int u, int l, int r) {
    if (tr[u].cnt > 0) { // 如果当前节点所代表的区间被完全覆盖
        tr[u].len = all_y[r + 1] - all_y[l];
    } else if (l == r) { // 叶子节点且未被覆盖
        tr[u].len = 0;
    } else {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
}

void build(int u, int l, int r) {
    tr[u] = {0, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void upd(int u, int l, int r, int ql, int qr, int k) {
    if (ql <= l && r <= qr) {
        tr[u].cnt += k;
    } else {
        int mid = (l + r) >> 1;
        if (ql <= mid) upd(u << 1, l, mid, ql, qr, k);
        if (qr > mid) upd(u << 1 | 1, mid + 1, r, ql, qr, k);
    }
    pushup(u, l, r);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segs.push_back({x1, y1, y2, 1});
        segs.push_back({x2, y1, y2, -1});
        all_y.push_back(y1);
        all_y.push_back(y2);
    }

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

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

    int m = all_y.size();
    build(1, 0, m - 2); // m 个端点有 m-1 个基本区间，索引为 0 到 m-2

    long long ans = 0;
    for (size_t i = 0; i < segs.size() - 1; ++i) {
        int y1_idx = find(segs[i].y1);
        int y2_idx = find(segs[i].y2);
        if (y1_idx < y2_idx) {
            upd(1, 0, m - 2, y1_idx, y2_idx - 1, segs[i].k);
        }
        ans += tr[1].len * (segs[i + 1].x - segs[i].x);
    }

    cout << ans << endl;
    return 0;
}

5.2 矩形周长并（洛谷 P1856 Picture）

周长并比面积并更为复杂，需要利用正交分解。将周长分别投影、分解为水平周长和垂直周长： 1. 水平周长：在扫描线宽度移动时，当前状态下存在的独立的不相交覆盖线段段数为 $sc$。每段在上下边界均对周长有贡献。水平贡献为： $$\text{Horizontal_Len} = 2 \times tr[1].sc \times (x_{i+1} - x_i)$$ 2. 垂直周长：每步扫描线更新前后有效 $y$ 覆盖长度的绝对差值 $|len_{\text{after}} - len_{\text{before}}|$，正好对应本次新产生（或消逝）的垂直边。

为此，线段树除了维护覆盖层数 cnt 和总长 len，还需要维护： * sc：节点区间内不相交的连续覆盖段数量。 * lv, rv：节点区间的左右端点是否已被覆盖。

核心 Pushup 段合并逻辑

对左右子节点进行区间合并时，我们需要通过左右端点连通状态来动态更新 $sc$： $$tr[u].sc = tr[ls].sc + tr[rs].sc - (tr[ls].rv \land tr[rs].lv)$$

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 5005;
const int XE = MAXN * 2;
const int XT = XE * 4;

struct Event {
    int x;
    int y1, y2;
    int t; // 1 为左边界，-1 为右边界
    bool operator<(const Event& o) const {
        if (x != o.x) return x < o.x;
        return t > o.t; // 相同坐标，左边界优先
    }
};

struct Node {
    int cnt;
    long long len;
    int sc; // 不相交的连续段数
    bool lv, rv;
} tr[XT];

Event e[XE];
vector<int> ys;

int fid(int val) {
    return lower_bound(ys.begin(), ys.end(), val) - ys.begin();
}

#define ls (u << 1)
#define rs (u << 1 | 1)

void pu(int u, int L, int R) {
    if (tr[u].cnt > 0) {
        tr[u].len = ys[R + 1] - ys[L];
        tr[u].sc = 1;
        tr[u].lv = tr[u].rv = true;
    } else if (L == R) {
        tr[u].len = 0;
        tr[u].sc = 0;
        tr[u].lv = tr[u].rv = false;
    } else {
        tr[u].len = tr[ls].len + tr[rs].len;
        tr[u].lv = tr[ls].lv;
        tr[u].rv = tr[rs].rv;
        tr[u].sc = tr[ls].sc + tr[rs].sc;
        if (tr[ls].rv && tr[rs].lv) {
            tr[u].sc--; // 左右接触点均覆盖，则合并连续段
        }
    }
}

void ud(int u, int L, int R, int qL, int qR, int v) {
    if (qL <= L && R <= qR) {
        tr[u].cnt += v;
        pu(u, L, R);
        return;
    }
    int M = L + (R - L) / 2;
    if (qL <= M) ud(ls, L, M, qL, qR, v);
    if (qR > M)  ud(rs, M + 1, R, qL, qR, v);
    pu(u, L, R);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    int ec = 0;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        e[ec++] = {x1, y1, y2, 1};
        e[ec++] = {x2, y1, y2, -1};
        ys.push_back(y1);
        ys.push_back(y2);
    }

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

    sort(e, e + ec);

    long long ans = 0;
    long long lln = 0; // 上次总有效 y 轴覆盖长度
    int my = ys.size();

    for (int i = 0; i < ec; ++i) {
        if (i > 0) {
            // 累加水平周长
            ans += tr[1].sc * 2LL * (e[i].x - e[i - 1].x);
        }

        int y1x = fid(e[i].y1);
        int y2x = fid(e[i].y2);

        if (y1x < y2x) {
            ud(1, 0, my - 2, y1x, y2x - 1, e[i].t);
        }

        // 累加垂直周长
        ans += abs(tr[1].len - lln);
        lln = tr[1].len;
    }

    cout << ans << endl;
    return 0;
}

6. 进阶联系与拓展

6.1 CDQ 分治与三维偏序（洛谷 P3810）

三维偏序是 CDQ 分治的核心应用场景：对含有元素 $(a_i, b_i, c_i)$ 的偏序对计数。 1. 第一维 $a$ 排序去重。 2. 第二维 $b$ 使用 CDQ 双指针分治归并。 3. 第三维 $c$ 借由树状数组维护。由于 $c$ 的数值空间很大，在归并过程中插入树状数组前，必须对其进行坐标离散化。

6.2 离线处理与树状数组（洛谷 P1972 HH的项链）

题意：求区间 $[l, r]$ 内有多少个互不相同的数。
离线思路：将所有查询根据右端点 $r$ 升序排序。
双指针树状数组维护：从左向右扫描，每当遇到数值 a[i]，若之前出现过，从之前位置注销（add(prev_pos, -1)），并在当前位置增加贡献（add(i, 1)）。这样可以保证树状数组中只记录每个数值“最后一次出现”的位置。
离散化必要性：如果数值本身可达 $10^9$，则我们需要在离线前对其全部离散化，这样记录原数值上一次出现的 pos[a[i]] 辅助位置数组便能以 $O(1)$ 的小空间高效寻址。

7. 常见陷阱与避坑指南

7.1 如何判断需要离散化？

值域大而点稀疏：坐标数值远大于实际元素个数时（如坐标 $10^9$，但元素个数只有 $10^5$），几乎必然需要离散化。
只看序不看数值：只要判定偏序（如 $>$、$<$)，或等价传递（如 $=$、$\ne$)，不依赖绝对相减或加法量级时，离散化是安全的。
下标约束：计划使用的树状数组/线段树受制于大值域而无法开辟数组时。

7.2 去重与索引对齐

unique 盲区：std::unique 并没有从物理上裁剪 vector 空间，它仅执行覆盖前移。去重必须紧跟 erase。
1-based vs 0-based 对齐：std::lower_bound 相比起点 begin() 的偏移量从 0 开始。而树状数组通常不接收索引 0。此时在 getId() 中需要统一进行 +1 操作。
漏项离散化：如果离散化不完全（例如：只对原始数据进行了映射，而忘记把区间查询的 $l, r$ 端点一同扔进 all 中，极易导致 lower_bound 无法精确匹配或返回未定义的乱序，引发底层断言故障）。

8. 经典例题选讲

例题 A：洛谷 P3740 [HAOI2014] 贴海报 (区间离散化)

思路：将长度可达 $10^7$ 的板上，贴 $m \le 1000$ 张海报。区间覆盖求最终可见海报数。我们将端点 $l_i$ 与 $r_i + 1$ 收集起来进行区间左闭右开离散化，通过线段树倒序覆盖并查询非零区间来统计可见张数。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXM = 1005;

struct Poster {
    int l, r;
};

struct Seg {
    int s;  // 未被覆盖的基本区间个数
    bool t; // 懒标记
};

int n, m;
Poster p[MAXM];
vector<int> d; // 区间离散化
Seg tr[MAXM * 8];

void psh(int u, int l, int r) {
    if (tr[u].t) {
        tr[u << 1].t = tr[u << 1 | 1].t = true;
        tr[u << 1].s = tr[u << 1 | 1].s = 0;
        tr[u].t = false;
    }
}

void bld(int u, int l, int r) {
    tr[u].t = false;
    if (l == r) {
        tr[u].s = 1;
        return;
    }
    int mid = (l + r) >> 1;
    bld(u << 1, l, mid);
    bld(u << 1 | 1, mid + 1, r);
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

void upd(int u, int l, int r, int ql, int qr) {
    if (tr[u].s == 0) return;
    if (ql <= l && r <= qr) {
        tr[u].s = 0;
        tr[u].t = true;
        return;
    }
    psh(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) upd(u << 1, l, mid, ql, qr);
    if (qr > mid)  upd(u << 1 | 1, mid + 1, r, ql, qr);
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

int ask(int u, int l, int r, int ql, int qr) {
    if (tr[u].s == 0) return 0;
    if (ql <= l && r <= qr) return tr[u].s;
    psh(u, l, r);
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res += ask(u << 1, l, mid, ql, qr);
    if (qr > mid)  res += ask(u << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        cin >> p[i].l >> p[i].r;
        d.push_back(p[i].l);
        d.push_back(p[i].r + 1); // 左闭右开区间处理
    }

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

    int tot = d.size();
    bld(1, 1, tot - 1);

    int ans = 0;
    for (int i = m; i >= 1; --i) {
        int l = lower_bound(d.begin(), d.end(), p[i].l) - d.begin() + 1;
        int r = lower_bound(d.begin(), d.end(), p[i].r + 1) - d.begin();

        if (ask(1, 1, tot - 1, l, r) > 0) {
            ans++;
        }
        upd(1, 1, tot - 1, l, r);
    }

    cout << ans << endl;
    return 0;
}

9. 推荐刷题列表

题目名称	平台及 ID	核心知识点	难度及学习要领
【模板】扫描线	洛谷 P5490	扫描线、线段树、矩形面积并	基础必刷。练习区间离散化基础框架和事件排序技巧。
Picture	洛谷 P1856	扫描线、线段树、矩形周长并	进阶突破。深刻掌握 `pushup` 中不连续线段树区间状态合并逻辑。
HH的项链	洛谷 P1972	离线处理、树状数组、坐标去重	离线典范。掌握通过按右端点排序、动态消除前驱点权重的离线技巧。
三维偏序	洛谷 P3810	CDQ分治、坐标离散化、树状数组	CDQ 必刷模板。理解离散化在多维降维分治下的支撑作用。
贴海报	洛谷 P3740	区间离散化、线段树覆盖	理解经典 $r + 1$ 保序映射，解决大规模覆盖检测问题。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com