算法竞赛当中离散化算法的初步介绍和简单应用
如果一个当给定的编号数据范围过于大时，需要用到离散化算法来映射编号，原理大致与哈希表差不多，但是有差别
就比如10000，20000，300000...映射之后就是1代表10000，2代表20000，5代表300000....
主要看你怎么编号，就是把大数据编码为小数据，这个技巧还是很实用的，属于算法竞赛当中的基础内容
802.区间和（离散化 + 前缀和）（模板题）
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
−10^9≤x≤10^9
1≤n,m≤10^5
−10^9≤l≤r≤10^9
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5离散化的本质其实就是把大数据编号为小数据，然后通过二分查找找到我们所编码的那个值
可以先假设一下，如果这道题的数据范围最大是10^3怎么做？是不是就是一个非常简单的前缀和，但是一旦数据量到达10^9这种很大的数据时，就需要先离散化编号一下了
代码模板
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 3e5 + 10;
int a[N],b[N];
vector<int> alls;
vector<PII> query,add;
int n,m;
int find(int 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 l + 1;
}
int main()
{
cin >> n >> m;
for(int i = 0,x,c;i < n;i ++){
cin >> x >> c;
alls.push_back(x);
add.push_back(make_pair(x,c));
}
for(int i = 0,l,r;i < m;i ++){
cin >> l >> r;
alls.push_back(l),alls.push_back(r);
query.push_back(make_pair(l,r));
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto [x,w] : add) a[find(x)] += w;
for(int i = 1;i <= alls.size();i ++) b[i] = b[i - 1] + a[i];
for(auto [l,r] : query) cout << b[find(r)] - b[find(l) - 1] << endl;
for(int i = 1;i <= 8;i ++) cout << a[find(i)] << " ";
return 0;
}103.电影 （简单应用）
莫斯科正在举办一个大型国际会议，有 n 个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见，我们把世界上的所有语言用 1 到 10^9 之间的整数编号。
在会议结束后，所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有 m 部电影正在上映，每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影，可以让观影很开心的人最多。
如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。
输入格式
第一行输入一个整数 n，代表科学家的数量。
第二行输入 n 个整数 a1,a2…an，其中 ai 表示第 i 个科学家懂得的语言的编号。
第三行输入一个整数 m，代表电影的数量。
第四行输入 m 个整数 b1,b2…bm，其中 bi 表示第 i 部电影的语音采用的语言的编号。
第五行输入 m 个整数 c1,c2…cm，其中 ci 表示第 i 部电影的字幕采用的语言的编号。
请注意对于同一部电影来说，bi≠ci。
同一行内数字用空格隔开。
输出格式
输出一个整数，代表最终选择的电影的编号。电影编号 1∼m。
如果答案不唯一，输出任意一个均可。
数据范围
1≤n,m≤200000,
1≤ai,bi,ci≤10^9
输入样例：
3
2 3 2
2
3 2
2 3
输出样例：
2这道题思路很很明显了，如果没有大范围数据其实应该算是入门级别的题，只不过这道题需要离散化一下编号
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 6e5 + 10;
int a[N],b[N],c[N];
int cnt[N];
vector<int> alls;
int n,m;
int res = -1;
int find(int 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 l;
}
int main()
{
cin >> n;
for(int i = 0;i < n;i ++){
cin >> a[i];
alls.push_back(a[i]);
}
cin >> m;
for(int i = 0;i < m;i ++){
cin >> b[i];
alls.push_back(b[i]);
}
for(int i = 0;i < m;i ++){
cin >> c[i];
alls.push_back(c[i]);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i = 0;i < n;i ++) cnt[find(a[i])] ++;
// for(int i = 1;i <= 3;i ++) cout << i << ":" << cnt[find(i)] << " ";
// cout << endl;
int x = 0,y = 0,idx = 1;
for(int i = 0;i < m;i ++){
int A = cnt[find(b[i])],B = cnt[find(c[i])];
// cout << A << " " << B << endl;
if(A > x || (A == x && B > y)){
res = idx;
x = A, y = B;
}
idx ++;
}
cout << (res == -1 ? 1 : res) << endl;
return 0;
}1952.金发姑娘和N头牛（差分 + 离散化）
你可能听过关于金发姑娘和三只熊的经典故事。
然而，鲜为人知的是，金发姑娘最终成了一个农民。
在她的农场中，她的牛棚里有 N 头奶牛。
不幸的是，她的奶牛对温度相当敏感。
对于奶牛 i，使其感到舒适的温度为 Ai…Bi。
如果金发姑娘将牛棚的恒温器的温度 T 设置为 T<Ai，奶牛就会觉得冷，并会产出 X 单位的牛奶。
如果她将恒温器的温度 T 设置在 Ai≤T≤Bi，奶牛就会感到舒适，并会产出 Y 单位的牛奶。
如果她将恒温器的温度 T 设置为 T>Bi，奶牛就会觉得热，并会产出 Z 单位的牛奶。
正如所期望的那样，Y 的值始终大于 X 和 Z。
给定 X,Y,Z 以及每头奶牛感到舒适的温度范围，请计算通过合理设定恒温器温度，金发姑娘可获得的最大产奶量。
恒温器温度可设置为任何整数。
输入格式
第一行包含四个整数 N,X,Y,Z。
接下来 N 行，每行包含两个整数 Ai 和 Bi。
输出格式
输出可获得的最大产奶量。
数据范围
1≤N≤20000
0≤X,Y,Z≤1000
0≤Ai≤Bi≤10^9
输入样例：
4 7 9 6
5 8
3 4
13 20
7 10
输出样例：
31
样例解释
金发姑娘可以将恒温器温度设置为 7 或 8，这样会让奶牛 1 和 4 感到舒适，奶牛 2 感到热，奶牛 3 感到冷。
共可获得 31 单位牛奶。
这道题需要一点点思维，或者说需要有一定的刷题量，一旦算法与算法之间联合起来的时候就很不好想。就比如这个题，只会差分不行，只会离散化也不行，必须这两个算法都掌握的非常牢固
思路就是区间[0,A[i]]全部加X，区间[A[i],B[i]] 全部加Y......将值离散化即可
代码：
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 4e4 + 10;
int b[N],a[N];
vector<int> alls;
vector<PII> add;
int n,X,Y,Z;
int res = 0;
int find(int 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 l + 1;
}
int main()
{
cin >> n >> X >> Y >> Z;
for(int i = 0,l,r;i < n;i ++){
cin >> l >> r;
alls.push_back(l), alls.push_back(r);
add.push_back(make_pair(l,r));
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i = 0;i < n;i ++){
auto [l,r] = add[i];
b[1] += X;
b[find(l)] += Y - X;
b[find(r + 1)] += Z - Y;
b[alls.size() + 1] -= Z;
}
for(int i = 1;i <= alls.size();i ++){
a[i] = a[i - 1] + b[i];
res = max(res,a[i]);
}
cout << res << endl;
return 0;
}