【题目来源】
【题目描述】
曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
【输入格式】
给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。
【输出格式】
第一行一个整数，表示起火的信息条数 n。
接下来 n 行，每行两个整数 a，b，表示一个着火位置的起点和终点（注意：左闭右开）。
【数据规模与约定】
对于全部的测试点，保证 1≤n≤2×10^4，−2^31≤a<b<2^31，且答案小于 2^31。
【输入样例】
3
-1 1
5 11
2 9
【输出样例】
11
【算法分析】
● 可以看出，这道题给的区间相对较少，只有 2×10^4 组区间。但是，每组区间端点的值域很大，可达 2^31-(-2^31) 个整数，约 16GB 大小。显然，已超出算法竞赛的内存上限（通常在 64MB ~ 512MB 之间）。故若采用暴力法进行染色标记，根本行不通。因为，根本开不了这么大的数组。 因此可以通过离散化，将 n 组区间的左右端点进行映射，总共 n 组区间，每组区间两个数，即共有 2*n 个端点，所以只需要开 2*n 的数组大小即可。
● 区间端点的值域（−2^31≤a<b<2^31）含有负数，无法作为数组下标。所以，从这个角度看，也得进行离散化。
● 离散化是一种数据处理的技巧。通过离散化，可以将稀疏的大范围数据映射为紧凑的整数序列，同时保持数据相对大小关系不变，既节省空间又提升访问效率，特别适合需要频繁随机访问的场景。可以进行离散化的数据有大整数、浮点数、字符串等。
● 简单而言，常用的离散化算法步骤为“提取、排序、去重、映射”。
【算法代码：数组 + sort + STL map】
#include <bits/stdc++.h>
using namespace std;const int maxn=2e4+5;
int fi[maxn],se[maxn];
int a[maxn<<1],t[maxn<<1];
bool st[maxn<<1];
map<int,int> mp;
int len,cnt,ans;int main() {int n;cin>>n;for(int i=1; i<=n; i++) {cin>>fi[i]>>se[i];a[++len]=fi[i];a[++len]=se[i];}sort(a+1,a+len+1);for(int i=1; i<=len; i++) { //discretizationif(mp.find(a[i])==mp.end()) {t[++cnt]=a[i];mp[a[i]]=cnt;}}for(int i=1; i<=n; i++) { //Left-Closed Right-Openint le=mp[fi[i]];int ri=mp[se[i]];for(int j=le; j<ri; j++) {st[j]=true;}}for(int i=1; i<cnt; i++) {if(st[i]) ans+=(t[i+1]-t[i]);}cout<<ans<<endl;return 0;
}/*
in:
3
-1 1
5 11
2 9out:
11
*/
【参考文献】