当题⽬中数据的范围很⼤，但是数据的总量不是很⼤。此时如果需要⽤数据的值来映射数组的下标时，就可以⽤离散化的思想先预处理⼀下所有的数据，使得每⼀个数据都映射成⼀个较⼩的值。之后再⽤离散化之后的数去处理问题。
⽐如：[99, 9, 9999, 999999]离散之后就变成[2, 1, 3, 4]
【离散化模板⼀】排序+去重+⼆分离散化之后的值
// 离散化模板⼀：排序 + 去重 + ⼆分查找离散之后的结果
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + 10; int n;
int a[N];
int pos; // 标记去重之后的元素个数
int disc[N]; // 帮助离散化 // ⼆分 x 的位置
int find(int x)
{ int l = 1, r = pos; while(l < r) { int mid = (l + r) / 2; if(disc[mid] >= x) r = mid; else l = mid + 1; } return l;
} int main()
{ cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; disc[++pos] = a[i]; } // 离散化 sort(disc + 1, disc + 1 + pos); // 排序 pos = unique(disc + 1, disc + 1 + pos) - (disc + 1); // 去重 for(int i = 1; i <= n; i++) { cout << a[i] << "离散化之后：" << find(a[i]) << endl; } return 0;
}
【离散化模版⼆】排序+使⽤哈希表去重并且记录离散化之后的值
// 离散化模板⼆：排序 + 哈希表去重以及记录最终的位置
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;const int N = 1e5 + 10; int n;
int a[N];
int pos; // 标记去重之后的元素个数
int disc[N]; // 帮助离散化
unordered_map<int, int> id; // <原始的值, 离散之后的值> int main()
{ cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; disc[++pos] = a[i]; } // 离散化 sort(disc + 1, disc + 1 + pos); // 排序 int cnt = 0; // 当前这个值是第⼏号元素 for(int i = 1; i <= pos; i++) { int x = disc[i]; if(id.count(x)) continue; cnt++; id[x] = cnt; } for(int i = 1; i <= n; i++) { cout << a[i] << "离散化之后：" << id[a[i]] << endl; } return 0;
}
【注意事项】
- 离散化是⼀种「处理数据的技巧」，模版其实不⽤背，根据算法思想就可以实现。并且实现离散化的⽅式也可以在上述模板的基础上「修改」，使⽤的时候千万「不要⽣搬硬套」（⼤家也会看到有些题解⾥⾯是借助「结构体」离散化的，但是核⼼的思想都是⼀样的）；
- 前期学习离散化的时候可能会被「绕」进去，会把「离散前」和「离散后」的值搞混，分不清楚是⽤离散前的值还是离散后的值。觉得迷惑是「很正常」，⼀定要根据离散化的原理「画图」分析整个流程。搞清楚每⼀个变量的作⽤以及达到的⽬的，就不会那么迷
P1496 火烧赤壁 - 洛谷
抛开数据范围不看，这就是⼀道「差分」题⽬：
- 给定⼀个区间，我们可以全部执⾏+1 操作；
- 最后看看整个数组中，⼤于0 的位置有多少个。
因此可以创建⼀个原数组的「差分」数组，然后执⾏完「区间修改」操作之后，还原原数组，「统计⼤于0 」的区间⻓度。
但是，这道题的「数据范围」不允许我们直接差分，因为「开不了那么⼤」的数组；即使能开那么⼤的数组，「时间」也不够⽤。
我们发现，区间的范围虽然很⼤，区间的「个数」却只有2 × 10^4 级别。此时我们就可以：
- 先将所有的「区间信息」离散化；
- 然后在「离散化的基础」上，处理所有的「区间修改」操作；
- 处理完之后找出「原始数组对应的区间端点」，计算相应的「⻓度」
#include <bits/stdc++.h>
using namespace std;const int N = 2e4 + 10;int n;
int a[N], b[N];int pos;
int disc[N * 2];
unordered_map<int, int> id;
int f[N * 2];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i];disc[++pos] = a[i];disc[++pos] = b[i];}//离散化sort(disc+1, disc+1+pos);pos = unique(disc+1, disc+1+pos) - (disc+1); //去重int cnt = 0;for (int i = 1; i <= pos; i++){int x = disc[i];if (id.count(x)) continue;id[x] = i;}//离散化的基础上做差分for (int i = 1; i <= n; i++){int l = id[a[i]], r = id[b[i]];f[l]++;f[r]--;}//还原数组for (int i = 1; i <= pos; i++) f[i] += f[i-1];//统计结果int ret = 0;for (int i = 1; i <= pos; i++){int j = i;while (j <= pos && f[j] > 0) j++;//i-jret += disc[j] - disc[i];i = j;}cout << ret << endl;return 0;
}
P3740 [HAOI2014] 贴海报 - 洛谷
根据题意「模拟」即可。
由于「区间的⻓度」很⼤，暴⼒模拟的时候会超时。但是我们发现，虽然区间⻓度很⼤，但是「区间的个数」是很少的，所以我们可以「离散化」处理⼀下区间的端点值，然后在「离散化的基础上」模拟覆盖情况。
离散化在离散「区间问题」的时候⼀定要⼩⼼！因为我们离散化操作会把区间缩短，从⽽导致丢失⼀些点。在涉及「区间覆盖」问题上，离散化会导致「结果出错」。
⽐如我们这道题，如果有三个区间分别为：[2,5],[2,3],[5,6] ，离散化之后为：[1,3],[1,2],[3,4] ，
区间覆盖如图所⽰：
![![[Pasted image 20250406135605.png]]](https://i-blog.csdnimg.cn/direct/8720d012982b416e8e563a5451465f4e.png)
为了避免出现上述情况，我们可以在离散化的区间[x,y]时，不仅考虑x，y这两个值，也把「
x+1，y+1 」也考虑进去。此时「单个区间内部」就出现空隙，「区间与区间之间」也会出现空
隙。就可以避免上述情况出现。
可⻅，离散化之后可能会导致结果错误，使⽤的时候还是需要「谨慎」⼀点
#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n, m;
int a[N], b[N];int pos;
int disc[N * 4];
unordered_map<int, int> id;int w[N * 4]; //海报墙
bool st[N * 4]; //标记哪些数字出现过int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){cin >> a[i] >> b[i];disc[++pos] = a[i]; disc[++pos] = a[i] + 1;disc[++pos] = b[i]; disc[++pos] = b[i] + 1;}sort(disc+1, disc+1+pos);int cnt = 0;for (int i = 1; i <= pos; i++){int x = disc[i];if (id.count(x)) continue;cnt++;id[x] = cnt;}//模拟for (int i = 1; i <= m; i++){//离散化之后的值a[i]-b[i]int l = id[a[i]], r = id[b[i]];for (int j = l; j <= r; j++){w[j] = i; }}//统计结果int ret = 0;for (int i = 1; i <= cnt; i++){int x = w[i];if (!x || st[x]) continue;ret++;st[x] = true;}cout << ret << endl;return 0;
}