核心逻辑与数学原理
在 NOIP 级别竞赛中，空间换时间（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)$ 寻址。
状态设计与算法推导
1. 坐标离散化（保序映射）
设原始序列为 $A = \{a_1, a_2, \dots, a_n\}$，值域极大。离散化的核心是构建一个严格单调递增的映射序列 $B$。
- 去重与排序：对 $A$ 的副本进行升序排序并去重，得到基准序列 $B = \{b_1, b_2, \dots, b_m\}$，其中 $m \le n$。
- 二分二段寻址：对于任意原始值 $a_i$，通过二分查找
std::lower_bound在 $B$ 中确定其排位 $idx$。映射关系为：
$$f(a_i) = \text{idx}, \quad \text{where } B[\text{idx}] = a_i$$
该过程保持了空间序关系：若 $a_i < a_j$，则 $f(a_i) < f(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$$
通过静态数组预分配内存，杜绝 std::unordered_map 在 Linux 环境下遭遇哈希碰撞退化为 $O(N)$ 的风险。
C++ 标准源码（要求是工业级代码）
以下源码演示了如何使用静态离散化与前缀和预处理，高效解决区间覆盖与离散频次统计问题。代码契合 NOIP/Linux 环境，通过 g++ -O2 极致优化。
#include <iostream>
#include <vector>
#include <algorithm>
using std::cin;
using std::cout;
using std::vector;
using std::sort;
using std::unique;
using std::lower_bound;
// 定义静态常量，严禁在循环中动态申请内存
const int MAXN = 200005;
int s[MAXN]; // 前缀和预处理数组
// 工业级离散化结构体封装
struct Discretizer {
vector<int> raw;
// 注入原始数据
void insert(int x) {
raw.push_back(x);
}
// 执行静态离散化预处理
void build() {
sort(raw.begin(), raw.end());
// unique 返回去重后的尾迭代器，erase 切除冗余空间
raw.erase(unique(raw.begin(), raw.end()), raw.end());
}
// 核心黑魔法：常数极小的二分寻址
int query(int x) const {
auto it = lower_bound(raw.begin(), raw.end(), x);
// 返回从 1 开始的离散化索引，为前缀和留出 0 号位
return static_cast<int>(it - raw.begin()) + 1;
}
int size() const {
return static_cast<int>(raw.size());
}
};
int main() {
// 强制断开 C++ 流同步，工业级快读前置条件
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
// 存储原始区间查询
struct Query {
int l, r;
};
vector<Query> q(static_cast<size_t>(m));
Discretizer d;
// 模拟坐标覆盖：读入区间并注入离散化器
for (int i = 0; i < m; ++i) {
cin >> q[i].l >> q[i].r;
d.insert(q[i].l);
d.insert(q[i].r);
}
// 构建离散化映射表，时空瓶颈在此打破
d.build();
// 利用差分算法进行区间预处理
for (int i = 0; i < m; ++i) {
int discrete_l = d.query(q[i].l);
int discrete_r = d.query(q[i].r);
s[discrete_l] += 1;
s[discrete_r + 1] -= 1; // 致命踩坑点：差分右界+1，若未开大 MAXN 空间此处必越界
}
// 前缀和还原状态空间
int total_points = d.size();
for (int i = 1; i <= total_points + 1; ++i) {
s[i] += s[i - 1];
}
// 输出每个经过离散化映射点的覆盖频次
for (int i = 1; i <= total_points; ++i) {
cout << s[i] << (i == total_points ? "" : " ");
}
cout << "\n";
return 0;
}NOIP 实战避坑指南
1. std::unordered_map 卡常与黑客构造数据退化
很多选手迷信 std::unordered_map 的平均 $O(1)$ 复杂度。NOIP 评测环境为 GCC，出题人极易通过特定的质数碰撞（Anti-Hash Test Data）将你的哈希表强行退化至 $O(N)$ 从而引发 TLE。
修正方案：涉及大值域非保序映射，要么手写拉链法哈希，要么引入自定义哈希函数重载 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)$。