7.离散化
主要思想：
有的数组，其元素的值域很大，比如数组中的元素范围很大，下标范围为[-10^9, 10^9]，但元素的个数很少，比如只有1000个元素。
有时（例如计数排序的思想），我们需要将元素的值，作为数组的下标来操作。此时不可能开一个2*10^9大小的数组。此时我们把这些元素，映射到下标从0（或者从1）开始的数组中。（也可以理解为对稀疏数组进行压缩）
或者理解为较大的数组下标与较小的数组下标建立映射关系
例如：
有一个数组a，存储1, 3, 100, 2000, 500000，此时若需要用该数组中元素值作为数组下标进行某种操作，这就意味着操作数组下标范范围很大但实际存储数据的位置就那么几个，所以我们把这个数组中的元素，映射到与[0, 1, 2, 3, 4]自然数相对应，即用一个新数组all[]，令all[0]=1,all[1]=3….all[4]=500000，这个映射的过程，称之为离散化。实际上离散化的是数组下标值，而不是实际数据，因为要将这些元素值作为下标去操作一个数组
离散化要点：
- 用数组all从下标0开始存储原数组a中的值，要求离散化数组all有序，且若有重复元素，可能需要去重(利用C++中的库函数实现排序和去重)
- 实现离散化，即得到离散化值（find函数返回数组下标），就能代表形成映射关系，元素值与数组下标对应
- 对离散化后的值进行操作：由于数组all已经排好序，故这里用二分查找x在数组all中的位置q（q:0~n-1，即实现离散化)
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> v;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int find(int x){
int l=0,r=v.size()-1;
while(l<r){
int mid=(l+r)/2;
if(v[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;
}
|
Acwing 802.区间和
实现思路：
- 先读入插入操作需要的数字（x,c）将其存储在add类型的数组当中，同时将x压入alls数组当中。再读入问询操作需要的数字（l,r）将其存储在query类型的数组当中，同时将l,r压入alls数组当中（注意这里想x,l,r都代表坐标轴位置）。
- 再对数组alls进行排序，去重操作，运用c++自带的sort函数对alls数组进行排序，再使用erase函数和unit函数对其进行去重操作。
- 再处理加数操作，利用二分查找，得到x在alls数组的位置q（注意加1，因为后续要算区间和即前缀和，数组从1开始），在创建一个数组a,a[q]就与坐标位置相对应（初始值为0），a[q]+c就表示对应坐标位置+c。
- 再求a数组前缀和数组，即s[i]=s[i-1]+a[i]，循环终止条件为i=alls.size()(因为二分查找最后一个位置加1)。
- 再求区间和，同加数操作，利用二分查找，得到l,r在alls数组的位置，通过前缀和数组求出区间和（s[r]-s[l-1]）。
其他理解：
AcWing 802. 区间和 - AcWing
http://t.csdnimg.cn/XPtTa
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
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=3e6+10;
vector<int> alls;
int a[N],s[N];
int n,m;
vector<PII> add,query;
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;
}
int main(){
cin>>n>>m;
while(n--){
int x,c;
cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
while(m--){
int l,r;
cin>>l>>r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto item:add){
int q;
q=find(item.first);
a[q]+=item.second;
}
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
for(auto item:query){
int l,r;
l=find(item.first);
r=find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
|