离散化=
第一章：基本概念与原理
1.1 什么是离散化？
离散化是一种将取值空间很大但数量有限的数值映射到连续小整数的技术，保持原始数据间的相对大小关系。
数学定义：
设原数据集为：
S={x1,x2,…,xn},xi∈RS = \{x_1, x_2, \dots, x_n\}, \quad x_i \in \mathbb{R} S={x1 ,x2 ,…,xn },xi ∈R
离散化映射为：
f:S→{1,2,…,m},m≤nf: S \rightarrow \{1, 2, \dots, m\}, \quad m \leq n f:S→{1,2,…,m},m≤n
满足保序性：
∀xi,xj∈S,xi<xj⇒f(xi)<f(xj)\forall x_i, x_j \in S, \quad x_i < x_j \Rightarrow f(x_i) < f(x_j) ∀xi ,xj ∈S,xi <xj ⇒f(xi )<f(xj )
1.2 为什么需要离散化？
实际问题场景：
1.3 应用场景
1. 统计类问题：求区间内不同数的个数
2. 离线查询：处理大量区间查询
3. 数据结构：树状数组、线段树的前置处理
4. 排序优化：减少比较开销
5. 哈希替代：用整数代替大数值
第二章：离散化算法步骤
2.1 完整流程图
2.2 示例演示
第三章：C++实现代码详解
3.1 方法一：STL标准库版（最常用）
代码说明：
变量 含义 作用 n 数据个数 输入数据的数量 a[] 原始数组 存储待离散化的原始数据 t[] 临时数组 用于排序和去重的副本 r[] 结果数组 存储离散化后的值 m 唯一值数量 去重后不同元素的数量
关键函数：
1. sort(t, t + n)
* 对数组t的[0, n)范围排序
* 时间复杂度：O(n log n)
* 必须排序，因为unique和lower_bound都需要有序数组
2. unique(t, t + n)
* 将相邻重复元素移到末尾
* 返回新的"逻辑末尾"指针
* 示例：[1,1,2,2,3] → 处理后[1,2,3,1,2]，返回指向第二个3的指针
* 必须配合sort使用，只能处理相邻重复
3. lower_bound(t, t+m, val)
* 二分查找第一个≥val的位置
* 要求数组有序
* 返回指针，减去t得到下标
* 时间复杂度：O(log m)
为什么+1？
* 下标从0开始，但很多问题中从1开始更方便
* 树状数组通常从1开始
* 从0开始：r[i] = idx
* 从1开始：r[i] = idx + 1
3.2 方法二：手写函数版（理解原理）
函数说明：
1. u(int l, int h) - 手写去重函数
* 参数：l起始位置，h结束位置（不包含）
* 原理：双指针法
* k：写入位置，i：读取位置
* 跳过所有重复元素，只保留第一个
* 时间复杂度：O(n)
2. b(int x, int m) - 手写二分查找
* 参数：x查找的值，m数组长度
* 返回：第一个≥x的位置
* 原理：标准二分查找
* 时间复杂度：O(log m)
算法流程：
3.3 方法三：结构体版（保留原始索引）
结构体方法特点：
1. 优点：
* 保留原始索引
* 一次排序完成
* 逻辑清晰
2. 结构体定义：
3. 算法流程：
4. 为什么从k=1开始？
* 排名从1开始
* 首次遇到新值给当前k
* 遇到相同值保持k不变
第四章：时间复杂度分析
方法 排序 去重 查找 总复杂度 空间复杂度 STL版 O(n log n) O(n) O(n log n) O(n log n) O(n) 手写版 O(n log n) O(n) O(n log n) O(n log n) O(n) 结构体版 O(n log n) 包含在排序中 O(n) O(n log n) O(n)
说明：
1. 排序是主要开销：O(n log n)
2. 去重：O(n)
3. 查找：
* STL/手写：n次二分查找，O(n log n)
* 结构体：一次遍历，O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
离散化是处理大值域、小数量问题的利器，掌握好离散化技巧能解决许多算法竞赛中的难题。
