[编程笔记]-Discretization离散化

前言

离散化和哈希差不多,但是还是有点区别。

  • 离散化中元素按顺序获取地址,与元素值没有直接关联;而哈希中元素地址就是元素数值通过哈希函数获得的。
  • 离散化需要二分预处理出所有地址,哈希是查询时在线计算地址。

如果有需要,可以看看哈希:

“[编程笔记]-Hash_Table哈希表”

简介

当遇到数值地址范围很大、数值量很少的问题时,可以使用离散化(或哈希)。

对原数组中所有地址进行排序、去重,然后记录每个地址对应的新地址,再用新地址储存元素,需要旧地址时以新地址为下标查询完成排序去重的数组即可。

模板

1
2
3
4
5
6
7
sort(vec.begin(),vec.end());//排序
vec.erase(unique(vec.begin(),vec.end()),vec.end());//去重
for(auto item:orgn){//用pair储存加值操作,这里执行
int x=bfind(item.first)//二分查询新地址
int c=item.second;//加值
a[x]+=c;
}

例题

AcWing802-区间和

这是一道融合了前缀和、二分查找、离散化的毒瘤好题,值得一刷。

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
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

const int N=3e5+5;//增值操作一次一个地址,查询操作一次两个地址,一共三倍的大小。

int n,m;
int x,c;
int l,r;
int a[N],s[N];

vector<int> locs;//储存所有地址
vector<pii> add,ask;

int bfind(int num){//这里本来应该有个二分,但是我懒( ̄︶ ̄)不会的可以去二分那一篇笔记看最后的拓展
return lower_bound(locs.begin(),locs.end(),num)-locs.begin()+1;//之所以加一是为了方便前缀和
}

void dis(){
sort(locs.begin(),locs.end());
locs.erase(unique(locs.begin(),locs.end()),locs.end());
for(auto item:add){
x=bfind(item.first);
c=item.second;
a[x]+=c;
}
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&c);
add.push_back({x,c});
locs.push_back(x);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
ask.push_back({l,r});
locs.push_back(l);
locs.push_back(r);
}
dis();//离散化
for(int i=1;i<locs.size()+1;i++){//因为所有地址手动加了1,所以最大值也要加1。
s[i]=s[i-1]+a[i];
}
for(auto item:ask){
l=bfind(item.first);
r=bfind(item.second);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}

完结撒花o( ̄︶ ̄)o


[编程笔记]-Discretization离散化
http://githarlem.github.io/2024/07/31/Discretization/
作者
Harlem
发布于
2024年7月31日
更新于
2024年8月2日
许可协议