讲义书架/基础算法
基础算法

离散化

保序映射、区间长度与边界保留

6个章节
查看本篇目录一、标准离散化：核心三步法1. 数组去重原理 (std::unique)2. 坐标映射 (std::lower_bound)3. 标准模板实现二、离散化的两大核心变体与避坑点1. 单点保序映射（数值大小关联）2. 区间离散化与“虚假相邻”陷阱（距离与覆盖关联）三、实战模型解析1. 模型一：单点离散化 + 树状数组求逆序对 (洛谷 P1908)2. 模型二：区间端点离散化与线段覆盖 (洛谷 P1496 火烧赤壁)四、离散化的逆向查询与灵活二分1. 还原原坐标：原值一直都在2. 阈值查询：没见过的 $X$ 怎么查？五、选型小练习：点与线段的直觉判定六、渐进式实战练习题单1. 第一阶梯：单点映射与数据结构结合2. 第二阶梯：区间离散化与线段差分3. 第三阶梯：覆盖顺序与间隙保留

在许多算法与数据结构问题中，数据的取值范围极大（如 ai∈[−109,109]a_i \in [-10^9, 10^9]），但实际参与处理的元素个数 nn 却较小（如 n≤105n \le 10^5）。若直接以数值作为下标开数组或建立树状数组、线段树，会导致空间爆炸或无法寻址。

离散化的物理本质：在不改变数据之间相对大小顺序的前提下，将无限或极大的值域映射到 [1,m][1, m]（m≤nm \le n）这样连续的、紧凑的整数下标空间中。

一、标准离散化：核心三步法

标准单点离散化的处理流水线分为三步：排序 →\to 去重 →\to 二分查秩。

1. 数组去重原理 (std::unique)

std::unique 本身只消除相邻的重复元素。为了在离散化中完成全局去重，我们先排序，让相同的值排在一起，再调用 unique。它把有效元素移到数组前部，并返回有效区间的尾后迭代器；不会缩小原数组，也不应再使用尾部无效区间中的内容。

在 1-based 数组体系下：

  • 排序：sort(b + 1, b + n + 1);

  • 去重并获取唯一元素个数 mm：m = unique(b + 1, b + n + 1) - (b + 1);

    去重后的元素存放在 b[1 ... m] 中，严格单调递增。

2. 坐标映射 (std::lower_bound)

去重后，若要求原数组某个值 xx 映射后的新编号（即其在保序数组中的排名），直接在 b[1 ... m] 上进行二分查找：

C++
int id = lower_bound(b + 1, b + m + 1, x) - b;

当 xx 已经收集进 b 时，id 落在 [1,m][1,m] 内，并且相同的值得到相同的编号。若 xx 没有被收集，lower_bound 返回的是插入位置，可能等于 m+1m+1，不能直接当成某个已有值的编号。

保留的是大小与相等关系，不是原始距离，也不是原数组的位置发生排序。 例如原序列 [40,−10,40,7,109,7][40,-10,40,7,10^9,7] 的离散化结果为 [3,1,3,2,4,2][3,1,3,2,4,2]。

离散化三步法：排序、去重、查秩，相同值映射为相同编号

3. 标准模板实现

C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int a[N],b[N];

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]; // 拷贝副本作映射基准
	}
	sort(b+1,b+n+1);
	int m=unique(b+1,b+n+1)-(b+1);
	
	// a[i] 映射为离散化后的值
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<(i==n?"":" ");
	}
	cout<<"\n";
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

二、离散化的两大核心变体与避坑点

1. 单点保序映射（数值大小关联）

若问题仅关心元素间的偏序关系（即 ai<aja_i < a_j 是否成立），直接套用上述三步法即可。典型场景如：离散化后利用树状数组或线段树统计逆序对、最长上升子序列（LIS）。

2. 区间离散化与“虚假相邻”陷阱（距离与覆盖关联）

区间问题要先分清：我们维护的是整数点的覆盖状态，还是连续线段的真实长度。离散化后相邻的编号，不代表原坐标相邻，也不代表相距 11。

典型错误示例：只保留端点，漏掉中间的覆盖状态。

在整数点覆盖模型中，依次涂色：

  • 先涂 A:[1,20]A:[1,20]；
  • 再涂 B:[1,10]B:[1,10]；
  • 最后涂 C:[12,20]C:[12,20]。

最终，点 1111 仍由 AA 覆盖，所以能看见 A,B,CA,B,C 三种标记。

若只保留端点 {1,10,12,20}\{1,10,12,20\}，这四个点的最终标记是 B,B,C,CB,B,C,C，就会漏掉只在中间出现的 AA。

解决方案按维护对象区分：

  • 方法 A（插点法，保留整数点覆盖状态）：对排好序的相邻原坐标，若 b[i]−b[i−1]>1b[i]-b[i-1]>1，在中间补一个代表点，例如 b[i−1]+1b[i-1]+1，再统一建立编号。本例补入 1111 后，就能保留 AA 的可见状态。代表点不能直接当作该间隙的真实长度。
  • 方法 B（左闭右开元线段法，维护长度）：只收集端点也可以正确计算连续长度。关键是把一个下标 ii 看作一段 [b[i],b[i+1])[b[i],b[i+1])，该段长度为 b[i+1]−b[i]b[i+1]-b[i]。例如 [1,10)[1,10) 与 [12,20)[12,20) 的端点压缩后，未覆盖段 [10,12)[10,12) 仍有独立的位置，总覆盖长度为 9+8=179+8=17。

两种边界不要混用： 若题目给的是整数闭区间 [l,r][l,r]，可以把它转成 [l,r+1)[l,r+1) 再按段处理，并注意 r+1r+1 的溢出。若题目本来求连续区间 [l,r)[l,r) 的长度，就保留 l,rl,r，不能额外加一。

整数点覆盖的端点压缩：补入间隙代表点11，保留仍可见的A

三、实战模型解析

1. 模型一：单点离散化 + 树状数组求逆序对 (洛谷 P1908)

场景：求长度为 nn 的序列中，满足 i<ji < j 且 ai>aja_i > a_j 的数对数量。n≤5×105n \le 5 \times 10^5，ai≤109a_i \le 10^9。

推导：

数值高达 10910^9，无法直接将 aia_i 作为树状数组的下标。将原序列离散化为 [1,m][1, m] 范围内的整数后，数值的相对大小关系严格不变。从右向左扫描序列，每次查询树状数组中前缀和 ∑k=1ai−1cnt[k]\sum_{k=1}^{a_i-1} \text{cnt}[k]，然后将 aia_i 插入树状数组。

为什么查询 a[i]-1？ 逆序对要求严格大于，右侧与当前值相等的元素不能计入；树状数组维护的是右侧已处理元素的频次，所以先查询，再插入当前值。

逆序对：从右向左扫描，查询严格更小的秩，先查再插入

C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;

int a[N],b[N],tr[N];
int n,m;

int lowbit(int x){
	return x&-x;
}

void modify(int x,int c){
	for(int i=x;i<=m;i+=lowbit(i)) tr[i]+=c;
}

int query(int x){
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i)) sum+=tr[i];
	return sum;
}

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	}
	
	int ans=0;
	// 倒序遍历树状数组统计逆序对
	for(int i=n;i>=1;i--){
		ans+=query(a[i]-1);
		modify(a[i],1);
	}
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

2. 模型二：区间端点离散化与线段覆盖 (洛谷 P1496 火烧赤壁)

场景：数轴上有 nn 个左闭右开区间 [Ai,Bi)[A_i,B_i) 被点燃（−231≤Ai<Bi≤231−1-2^{31} \le A_i < B_i \le 2^{31}-1），求数轴上最终被燃烧的总长度。

推导：

直接将每个区间的起点 AiA_i 和终点 BiB_i 提取出来进行全局排序去重。

去重后得到序列 b[1…m]b[1 \dots m]。端点之间被划分为 m−1m-1 个基础区间块：[b[1],b[2]),[b[2],b[3]),…,[b[m−1],b[m])[b[1],b[2]),[b[2],b[3]),\dots,[b[m-1],b[m])。

在离散化后的下标上利用差分数组 d 进行打标：对于区间 [Ai,Bi)[A_i,B_i)，找到其在 bb 数组中对应的离散化下标 l,rl, r，执行 d[l]++ 与 d[r]--。

扫描前缀和：若某段微元 [b[i],b[i+1])[b[i],b[i+1]) 的差分前缀和 >0>0，说明该段被至少覆盖一次，累加真实长度 b[i+1]−b[i]b[i+1]-b[i]。即使覆盖多次，该段也只计入一次。

区间离散化与差分：保留未覆盖间隙，用原坐标差计算总长度17

C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=40005;

struct Node{
	int l,r;
}seg[N];

int b[N],d[N];

void solve(){
	int n;
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>seg[i].l>>seg[i].r;
		b[++cnt]=seg[i].l;
		b[++cnt]=seg[i].r;
	}
	sort(b+1,b+cnt+1);
	int m=unique(b+1,b+cnt+1)-(b+1);
	
	for(int i=1;i<=n;i++){
		int l=lower_bound(b+1,b+m+1,seg[i].l)-b;
		int r=lower_bound(b+1,b+m+1,seg[i].r)-b;
		d[l]++;
		d[r]--; // 左闭右开微元区间差分
	}
	
	int ans=0,sum=0;
	for(int i=1;i<m;i++){
		sum+=d[i];
		if(sum>0){
			ans+=b[i+1]-b[i]; // 累加对应的实际物理长度
		}
	}
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

四、离散化的逆向查询与灵活二分

在很多高级数据结构题中，我们不仅要“把大数变成小数”，还要能“找回原来的数”，甚至面对一开始没见过的查询条件。

1. 还原原坐标：原值一直都在

离散化把原值映射成了秩（编号）。如果后续线段树查到了某个区间的最优解所在位置是编号 id，怎么输出它原本的坐标？ 完全不需要额外的映射数组，去重后的 b 数组本身就是编号到原值的完美字典。

因为映射过程是 id = lower_bound(b + 1, b + m + 1, x) - b，那么对应地，b[id] 就是原值 x。 例如原坐标为 [10, 50, 100]，映射后编号为 1, 2, 3。若最终答案落在编号 2，原坐标就是 b[2] = 50。

2. 阈值查询：没见过的 XX 怎么查？

场景：你已经把给定的数组 AA 离散化，并建好了树状数组（内部结构依赖 b[1...m]）。突然来了一个新查询：“统计当前数组中小于等于 XX 的元素个数”，而这个 XX 之前并没有出现在数组 AA 中，不在离散化池子里。现在重新把 XX 加入去重并重建树状数组，代价太大了。

推导： 其实根本不用把 XX 加进 b 数组。既然 b[1...m] 是单调递增的，我们只需要在 b 数组中找到最后一个小于等于 XX 的原值编号即可。利用 upper_bound 找第一个严格大于 XX 的位置，再往前退一格：

C++
// 在已去重的 b[1...m] 中，找原值 <= X 的最大编号
int id = upper_bound(b + 1, b + m + 1, X) - b - 1;

// 查询树状数组中编号 <= id 的频次和，就等价于查询原值 <= X 的频次和
int ans = query(id);

实战例子： 离散化数组 b 是 [10, 20, 50, 100]（分别对应编号 1, 2, 3, 4）。 查询有多少个数 ≤30\le 30。 upper_bound 找 30，会指向 50（对应位置 3）。减去 1 得到编号 2。 这就意味着：“原值 ≤30\le 30” 这个条件，在离散化的世界里，精准等价于“编号 ≤2\le 2”。直接去查 query(2) 即可，完美绕开了重新离散化。 （注：如果 XX 比所有数都小，id 算出来是 00，树状数组查 query(0) 恰好返回 00，非常安全。）

五、选型小练习：点与线段的直觉判定

在动手做综合大题前，先花一分钟测试自己的直觉：遇到区间题，我们该用单点映射，还是线段微元长度，还是会掉进虚假相邻陷阱？

  • 情景 A：数轴上有 10510^5 个哨塔，坐标很大。有 QQ 次询问，每次问坐标区间 [L,R][L, R] 内有几个哨塔。 判定：这是单点映射。只关心哨塔的相对位置，不用管它们隔得多远。用离散化把已知哨塔坐标压缩，查询时利用刚刚学的灵活二分把 L,RL, R 转成离散编号 l,rl, r，树状数组前缀和相减即可。
  • 情景 B：施工队在公路上修路，给出每天修路的起止坐标 [Li,Ri][L_i, R_i]（允许重叠），求最终公路修好的总里程。 判定：这是线段长度。直接把所有端点放到一起排序去重，把相邻端点跨度 [b[i],b[i+1])[b[i], b[i+1]) 看作微元段。如果该微元段被覆盖，就累加其实际物理长度 b[i+1]−b[i]b[i+1] - b[i]。
  • 情景 C：一面极长的墙，按整数块划分。每天用不同颜色的海报覆盖墙面 [Li,Ri][L_i, R_i] 块。全部贴完后，墙上能看到多少种不同的颜色？ 判定：这就是必须警惕的整数点覆盖（虚假相邻）！如果只把端点离散化，中间未被端点切分但仍残留着底色的海报段会被无情吞没。必须在不相邻的端点之间插点（补 b[i-1]+1），或者把 [Li,Ri][L_i, R_i] 转换成左闭右开 [Li,Ri+1)[L_i, R_i+1) 纳入边界池。

六、渐进式实战练习题单

1. 第一阶梯：单点映射与数据结构结合

  1. 洛谷 B3694 【模板】数列离散化
    • 考点：排序、去重、查秩。
    • 思路：直接练习三步法。注意本题有多组数据，先读入 TT，再执行 TT 次 solve()；前面的标准模板演示的是单组输入。
  2. 洛谷 P1097 [NOIP 2007 提高组] 统计数字
    • 考点：基础去重与频次统计。
    • 思路：对大数值进行排序后统计相邻同值块长度，或者离散化后开桶记录出现次数。
  3. 洛谷 P1908 逆序对
    • 考点：单点离散化 + 树状数组/归并排序。
    • 思路：将数值映射至 [1,m][1,m]，用树状数组维护前缀频次，相等值不计入逆序对。
    • 也可以不做离散化，直接在归并时统计，见《排序算法进阶》第一节。
  4. 洛谷 P1966 [NOIP 2013 提高组] 火柴排队
    • 考点：两序列的秩对应 + 位置映射 + 逆序对。
    • 思路：先由排序不等式确定同秩配对能够使平方差之和最小，再建立同秩元素的位置映射，用逆序对求最少相邻交换次数。原始高度决定距离的数值，但求最优配对及交换次数时只需保留秩关系。

2. 第二阶梯：区间离散化与线段差分

  1. 洛谷 P1496 火烧赤壁
    • 考点：区间端点离散化 + 差分前缀和。
    • 思路：按原题左闭右开区间建立微元段 [b[i],b[i+1])[b[i],b[i+1])，利用差分覆盖累计真实长度。
  2. 洛谷 P4122 [USACO17DEC] Blocked Billboard B
    • 考点：二维坐标离散化 / 矩形面积。
    • 思路：横纵坐标分别离散化，在小网格上标记广告牌与遮挡区域。每个有效格子累加 (x[i+1]−x[i])×(y[j+1]−y[j])(x[i+1]-x[i])\times(y[j+1]-y[j])，不能按格子个数当作面积；本题也可以直接求矩形交集。

3. 第三阶梯：覆盖顺序与间隙保留

  1. 洛谷 P3740 [HAOI2014] 贴海报
    • 考点：整数闭区间覆盖、后写覆盖前写、间隙状态保留。
    • 思路：端点间插入代表点后维护最后覆盖标记；也可以把整数闭区间 [l,r][l,r] 转为 [l,r+1)[l,r+1)，收集边界后按元区间维护。最后统计不同可见海报编号，而不是覆盖长度。
搜索全部54篇讲义的标题、目录与正文
点击结果进入讲义Esc 关闭