离散化
集训的时候，离散化这块明明很简单，但始终听不懂。现在回头学了第二遍，终于懂了，于是记录一下。
思路
由于离散化后会破坏数之间的具体大小关系，所以只有在只需要数的相对大小关系时可以离散化，同时意味着我们可以对原数组排序。
- 去重
- 查找原数组中某个数对应的，离散化后的数的位置
这里第二部查找时，由于排序后的数组有序，可以用二分来解决。
一般情况下，离散化只存在从原数组寻找离散化后的数组的操作，不存在反向搜索。
所以，在离散化后的任何操作，例如求前缀和或差分，都需要转化为对离散化后的数组的操作。
即原数组一般情况下已不可操作！！！
模板
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n ；+1从1开始映射；不+1从0开始映射
}
题目
火烧赤壁（洛谷P1496）
题目背景
曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
题目描述
给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。
输入格式
第一行一个整数，表示起火的信息条数 n。
接下来 n 行，每行两个整数 a, b，表示一个着火位置的起点和终点（注意：左闭右开）。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
3
-1 1
5 11
2 9
样例输出 #1
11
提示
数据规模与约定
对于全部的测试点，保证 1 \leq n \leq 2 \times 10^4，-2^{31} \leq a \leq b \lt 2^{31}，且答案小于 2^{31}。
思路
首先，此题可以使用差分解决，即将每次给的范围内的数的值都加1，最后统计值不是0的数的个数。
但是，由于此题 a、b 的范围过大，不能直接使用差分，否则会开的数组过大，同时数的总个数又不算太多，这时就需要使用离散化。
同时注意此题与原思路稍不同的地方：
由于这里我们离散化时，是将原数组排序并去重后，直接将处理后的数组的下标作为了离散化后的值，则此时我们就可以通过下标，反向找到离散化前的原值。这也是我之前理解不了的地方。
代码参考
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 2 * 2e4 + 10;//每组两个值，所以要开两倍
typedef long long ull;
typedef pair<ull, ull> PII;
vector<ull> alls;//待离散化数组
vector<PII> quest;//成对存储原数组 - 用于差分
int b[MAX];//差分数组
int a[MAX];//差分求和后的数组
int num;//离散化后的数组的总长
ull ans;
int find(int x)
{
int l = 0, r = num - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}//find函数用来查找原数对应的离散化后的数
int main()
{
int n = 0;
cin >> n;
for(int i = 0; i < n; i++)
{
ull l = 0, r = 0;
scanf("%lld %lld", &l, &r);
alls.push_back(l);
alls.push_back(r);
quest.push_back({ l, r });
}//读入 - 将左右端点都存入待离散化的数组，同时再分别存起来，方便之后处理
sort(alls.begin(), alls.end());//排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());//去重
num = alls.size();//求一下alls数组总长，避免多次重复求长
for (int i = 0; i < n; i++)
{
b[find(quest[i].first)] += 1;
b[find(quest[i].second)] -= 1;
}//差分
for (int i = 1; i <= num; i++) a[i] = a[i - 1] + b[i];//差分求和
int l = 0, r = 0;
for (int i = 1; i < num; i++)
{
if (a[i] && a[i - 1] == 0) l = i;
if (a[i] && a[i + 1] == 0) r = i + 1;
if (r > l)
{
ans += alls[r - 1] - alls[l - 1];//差分数组从1开始，但原数组对应从0开始，所以这里求原数组时要-1
l = r;
}
}//将差分后的数组对应至原数组，统计不是0的长度，l、r为左右端点
cout << ans << endl;
return 0;
}
评论区