核心逻辑与数学原理
空间换时间（Space-Time Trade-off）是突破时间复杂度瓶颈的最直接手段。其底层数学原理基于映射函数的常数级寻址能力。
朴素搜索的本质是在状态空间中进行遍历，时间复杂度通常为 $O(N)$ 或 $O(N^2)$。通过构建映射函数 $f(x) \to \text{Address}$，将数据域直接映射至内存物理地址，可以将查找、去重及频次统计的时间复杂度降低至 $O(1)$。
当原始数据值域 $\mathbb{U}$ 极大（如 $\mathbb{U} \in [-10^9, 10^9]$）且稀疏时，直接开辟数组会引发内存越界（MLE）。此时必须通过离散化（Discretization）或哈希（Hashing）进行保序或非保序的单射映射，将稀疏大值域压缩至紧凑的线性空间 $[1, N]$，从而在不破坏相对大小关系或唯一性的前提下，利用数组实现 $O(1)$ 寻址。
当原始数据值域 $\mathbb{U}$ 极大（如 $\mathbb{U} \in [-10^9, 10^9]$）且稀疏时，直接开辟数组会引发内存越界（MLE）。此时必须根据算法对元素顺序的需求，采用不同的空间映射策略：
-
坐标离散化（Discretization）：进行保序单射。将稀疏大值域压缩至紧凑的线性空间 $[1, K]$。它的核心在于严格保留元素间的相对大小关系（拓扑序），是后续配合树状数组、线段树进行区间维护、值域扫描的核心前置技术。
-
静态哈希（Hashing）：进行非保序散射。将极大值域通过哈希函数映射至固定的哈希桶空间。它会彻底破坏元素间的大小顺序，但能够以极高的效率实现 $O(1)$ 级别寻址，专用于解决纯粹的去重、存在性验证或频次统计问题。
状态设计与算法推导
1. 坐标离散化（保序映射）
设原始序列为 $A = \{a_1, a_2, \dots, a_n\}$，值域极大。离散化的核心是构建一个严格单调递增的基准序列 $B$。
- 去重与排序：对 $A$ 的副本进行升序排序并去重，得到基准序列 $B = \{b_1, b_2, \dots, b_m\}$，其中 $m \le n$。
- 二分寻址：对于任意原始值 $a_i原$，通过二分查找
lower_bound在 $B$ 中确定其排位 $idx$。映射关系为：
$$f(a_i) = \text{idx}, \quad \text{where } B[\text{idx}-1] = a_i \text{ (1-based index)}$$
优先采用 1-based 的场景：树状数组、前缀和、线段树
该过程保持了空间序关系：若 $a_i < a_j$，则 $f(a_i) < f(a_j)$。排序复杂度为 $O(N \log N)$，单次转换复杂度为 $O(\log N)$。
2. 静态哈希（非保序散射）
对于不需要维护大小关系、仅追求纯粹 $O(1)$ 存取的场景（如大整数去重、频次统计），直接采用静态数组模拟链式前向星结构的哈希表（拉链法）。 设哈希函数为 $H(x) = (x \bmod P + P) \bmod P$，其中 $P$ 为大质数。 这里两次取模是为了防止出现负数下标。 状态存储结构：
$$head[H(x)] \to nxt[i] \to nxt[j] \dots$$
通过静态数组预分配内存，杜绝 unordered_map 在 Linux 环境下遭遇哈希碰撞退化为 $O(N)$ 的风险。
算法模板
使用静态离散化与前缀和预处理，高效解决区间覆盖与离散频次统计问题。
#include <iostream>
#include <algorithm>
using cin;
using cout;
using sort;
using unique;
using lower_bound;
const int MAXM = 200005;
const int MAXN = MAXM * 2 + 5; // 离散化去重后最多 2*M 个点，严格开 2 倍空间防 RE
int l[MAXM], r[MAXM]; // 存储原始询问区间
int raw[MAXN], tot; // 离散化原值数组与指针（1-based）
int s[MAXN]; // 全局差分数组
int main() {
// 极致 I/O 优化
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
if (!(cin >> m)) return 0;
// 1. 读入区间并打平喂给离散化数组
for (int i = 1; i <= m; ++i) {
cin >> l[i] >> r[i];
raw[++tot] = l[i];
raw[++tot] = r[i];
}
// 2. 静态离散化预处理（排序与去重）
sort(raw + 1, raw + tot + 1);
tot = unique(raw + 1, raw + tot + 1) - (raw + 1);
// 3. 核心映射与差分打标记
// 几何线段并集视为左闭右开 [l, r)，标准差分为 s[l]++, s[r]--
for (int i = 1; i <= m; ++i) {
int disc_l = lower_bound(raw + 1, raw + tot + 1, l[i]) - raw;
int disc_r = lower_bound(raw + 1, raw + tot + 1, r[i]) - raw;
s[disc_l] += 1;
s[disc_r] -= 1;
}
long long total_length = 0; // 物理坐标差值可能极大，必须用 long long
int current_coverage = 0;
// 4. 前缀和扫描统计线段长度
// 离散点 i 到 i+1 之间的物理段为 [raw[i], raw[i+1])
for (int i = 1; i < tot; ++i) {
current_coverage += s[i];
if (current_coverage > 0) {
total_length += (long long)raw[i + 1] - raw[i];
}
}
cout << total_length << "\n";
return 0;
}从输入数据的物理现实来看，题目给的通常是闭区间 [L, R]；但在代码的算法逻辑中，把它视作左闭右开区间 [L, R) 来处理。
之所以这样处理，是因为我们在解决的是几何线段长度问题，而不是离散整点个数问题。我们可以从以下两个维度来彻底理清这个逻辑：
第一，为什么几何线段能直接等价为左闭右开？ 在数轴上，一段从 L 到 R 的连续线段，其几何长度是 R - L。在数学几何中，一个孤立的点其长度是 0。因此，闭区间 [L, R] 的长度、开区间 (L, R) 的长度、以及左闭右开区间 [L, R) 的长度，在几何拓扑上是完全相等的，全部都是 R - L。既然长度相等，为了程序写起来最舒服、最不容易出错，我们主动选择左闭右开模型。
第二，算法中写成 [L, R) 的巨大优势。
s[disc_l] += 1;
s[disc_r] -= 1;配合后文的循环扫描：
for (int i = 1; i < tot; ++i) {
current_coverage += s[i];
if (current_coverage > 0) {
total_length += (long long)raw[i + 1] - raw[i];
}
}不容易出现边界错位（±1 陷阱）
区间覆盖的两种映射模型
在处理区间覆盖时，必须引导学生分清“点覆盖”与“线段覆盖”的本质区别，否则极易产生原理性错误。
-
模型 A：连续线段几何覆盖（如：计算区间并集总长度） 若输入闭区间 $[L, R]$ 代表几何轴上的线段，其本质可视为左闭右开的连续集合 $[L, R)$。直接将 $L$ 与 $R$ 注入离散化器。离散化后，相邻两点 $B[i]$ 与 $B[i+1]$ 之间构成一个独立的线段段落。 差分操作：
s[query(L)] += 1,s[query(R)] -= 1。 长度累加：若该段落被覆盖，其实际物理长度为 $B[i+1] - B[i]$。 -
模型 B：离散点阵覆盖（如：统计哪些具体的整点被覆盖） 若输入闭区间 $[L, R]$ 代表整点集合。 差分操作：
s[query(L)] += 1,s[query(R) + 1] -= 1。此时离散化数组不仅要插入 $L$ 和 $R$，为防边界缺失，通常建议同时插入 $R+1$。
NOIP 实战避坑指南
1. unordered_map 卡常与黑客构造数据退化
很多选手迷信 unordered_map 的平均 $O(1)$ 复杂度。出题人极易通过特定的质数碰撞（Anti-Hash Test Data）将你的哈希表强行退化至 $O(N)$ 从而引发 TLE。
在 NOIP 采用的 GCC 编译器（C++ 标准库）中，为了追求运行速度，哈希表的内部实现非常纯粹，却也留下了两个致命的固定规律：
整型的哈希函数等于原值：如果你存入一个整数 x，GCC 默认的哈希函数不做任何混淆，直接返回 x 本身。
桶的个数是固定的质数：哈希表内部决定把数据分配到哪个桶，是用 哈希值 % 桶的总数。为了减少冲突，GCC 源码里直接硬编码了一个固定质数表（例如 126271、1000003 等）。随着你往 map 里存入的数据变多，哈希表扩容时，桶的总数会严格按照这个质数表里的下一个质数来开辟。
修正方案：涉及大值域非保序映射，要么手写拉链法哈希，要么引入自定义哈希函数重载 custom_hash，并使用高精度时间戳作为随机种子（chrono）扰动哈希桶分布。
2. 离散化去重边界与空间加倍膨胀
离散化通常伴随区间操作。若每个区间有两个端点 $L$ 和 $R$，离散化数组的实际有效大小最大可达 $2M$。选手若习惯性以 $N$ 作为数组上界开辟空间，直接引发运行时段错误（RE）。
修正方案：定义全局静态数组时，必须根据离散化元素的实际最大上限（通常为 $2 \times \text{Query\_Size}$）开辟空间，并预留至少 $5$ 个单位的安全边界以防差分操作如 r + 1 发生越界。
经典 NOIP/洛谷 真题
1. 洛谷 P1496 火烧赤壁
- 题意描述：给出 $N$ 个闭区间 $[A_i, B_i]$，求这些区间的并集总长度。其中 $N \le 20000$，坐标范围 $[-10^9, 10^9]$。
- 问题本质：极大稀疏值域下的区间长度并集统计。
- 核心解题思路：值域高达 $2 \times 10^9$，无法直接开辟布尔数组。将所有的左右端点 $A_i, B_i$ 放入离散化器进行排序去重。离散化后，原轴被切分成若干独立小段。遍历所有原始区间，在离散化后的坐标轴上进行标记（或采用差分）。最后遍历离散坐标轴，若某段被覆盖，则将其真实的物理长度
raw[i] - raw[i-1]累加至答案。时间复杂度降低至 $O(N \log N)$。
2. 洛谷 P1908 逆序对
- 题意描述：给出一个长度为 $N$ 的序列，求满足 $i < j$ 且 $a_i > a_j$ 的数对总数。$N \le 5 \times 10^5$，$a_i \le 10^9$。
- 问题本质：利用树状数组配合空间映射动态维护前缀频次。
- 核心解题思路：常规解法是利用树状数组动态维护值域。但 $a_i$ 值域过大，树状数组无法直接开辟。逆序对仅关注元素间的相对大小关系（拓扑序），因此直接对原数组进行保序离散化映射，将值域压缩至 $[1, N]$。从后往前遍历离散化后的数组，在树状数组中查询比当前元素小的元素个数并累加，随后将当前元素插入树状数组。空间复杂度成功由 $O(\mathbb{U})$ 优化至 $O(N)$。