底层原理
有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以建立这段数据和自然数的映射关系，（value -> index），通过建立新索引，来缩小目标区间，使得可以进行一系列连续数组可以进行的操作比如二分，前缀和等…
离散化问题解题模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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
}
|
注： 代码来源于y总！
题目练习
第一题 （来自acwing）
假定有一个无限长的数轴，数轴上每个坐标上的数都是 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$
输入样例
1
2
3
4
5
6
7
|
3 3
1 2
3 6
7 5
1 3
4 6
7 8
|
输出样例
代码示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=300010;//坐标x的数量上限为1e5，两个坐标l,r的数量上限也为1e5,所以加起来为3*le5;
typedef pair<int,int> PII;//pair<int,int>类似于结构体的简写版，typedef定义了一个新的类型PII(跟结构体定义了一个结构体类型然后使用相似)
int a[N],s[N];
vector<int> alls;
vector<PII> add,query;
//使用二分查找x所在的位置，此时是alls(x,l,r)排好序的,返回的坐标也会是按照x的大小所给出的；
int find(int x)
{
int l=0,r=alls.size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(alls[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;//因为后续要使用前缀和，所以返回的坐标要加上1；
}
int main()
{
int n,m;cin>>n>>m;
//分别将要操作的四组数据记录在add和query中，将l，r，x的坐标值保存在alls中；
for(int i=0;i<n;i++)
{
int x,c;
cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
for(int i=0;i<m;i++)
{
int l,r;
cin>>l>>r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
//将alls进行排序，并将重复的操作删除掉(如进行了两次在x的增值操作，应该去掉一个x保持平衡)；
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
//一个迭代器从1开始直到末尾结束，itdm.first是x，second是c(在上方循环中可知)；
for(auto itdm : add)
{
int x;
x=find(itdm.first);
a[x]+=itdm.second;
}
//只循环x是因为x的坐标加上了值，而l，r可能有(l或r与x的值相同)，且定义全局变量数组，其余值默认为0，故可以方便计算；
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
for(auto itdm : query)
{
int l,r;
l=find(itdm.first);//找出l，r在a中的坐标
r=find(itdm.second);
printf("%d\n",s[r]-s[l-1]);//前缀和上方已计算，所以可直接输出，记得加上换行符！
}
return 0;
}
|
第二题（来自洛谷B3694）
数列离散化
题目描述
给定一个长度为 $n$ 的数列 $a$。定义 $\mathrm{rank}(i)$ 表示数列 $a$ 中比 $a_i$ 小的不同数字个数再加一。
对 $1 \leq i \leq n$，现在请你求出所有的 $\mathrm{rank}(i)$。
输入格式
本题单测试点内有多组测试数据。
输入的第一行是一个整数，表示数据组数 $T$。接下来依次给出每组数据的信息：
第一行是一个整数，表示数列长度 $n$。
第二行有 $n$ 个整数表示数列 $a$，第 $i$ 个整数表示 $a_i$。
输出格式
对每组数据，输出一行 $n$ 个整数，用空格隔开，依次表示 $\mathrm{rank}(1)$ 到 $\mathrm{rank}(n)$。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
|
3
3
1 2 3
5
1 6 2 2 7
4
-1 -2 -3 -3
|
样例输出 #1
1
2
3
|
1 2 3
1 3 2 2 4
3 2 1 1
|
提示
数据规模与约定
对全部的测试点，保证 $1 \leq T \leq 5$，$1 \leq n \leq 10^5$，$-10^9 \leq a_i \leq 10^9$。
代码示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> alls; // 存储所有待离散化的值
// 自定义二分查找函数，找到 x 在离散化数组中的位置
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; // 将索引映射到 1, 2, ... n
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
alls.clear();
// 读取输入，同时加入到 alls 中以便离散化
for (int i = 0; i < n; i++) {
cin >> a[i];
alls.push_back(a[i]);
}
// 对 alls 进行排序和去重，完成离散化
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 计算每个元素的排名
for (int i = 0; i < n; i++) {
int rank = find(a[i]); // 使用自定义的二分查找获取排名
cout << rank << " ";
}
cout << endl;
}
return 0;
}
|
总结
注意掌握离散化的核心原理和解题模板，才能更好地解决问题！最后谢谢大家的支持！