[编程笔记]-Discretization离散化

前言

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

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

如果有需要，可以看看哈希：

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

简介

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

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

模板

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-区间和

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

#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