离散化-c++

离散化：

一、使用情景

值域大 e.g. 0~1e9
个数少 e.g. 0~1e5

二、使用方法

将数组中的数映射到从0开始的自然数

a[ ]:1、3、100、2000、50000
映射到从0开始的自然数：0，1，2，3，4

这个过程就是离散化

三、两个问题：

1. a数组中最开始可能有重复元素，需要去重

vector<int> alls;//存储所有待离散化的值
sort(alls.begin(),alls.end());//将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重

unique函数 将vector中所有的重复元素去重，并且返回去重vector的的尾端点
再用erase函数将vector中所有的重复元素去除即可

2. 如何算出x离散化后的值是多少

因为a数组是有序的，我们进行保序离散化，实际上就是把值映射到下标,
所以要找出x在a数组中对应的下标是多少

四、代码模板

vector<int> alls;//存储所有待离散化的值
sort(alls.begin(),alls.end());//将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重

//二分求出x对应的离散化的值
int find(int x){
    int l = 0,r = all.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,3...n
}

五、题目

802. 区间和 - AcWing题库

1. n个操作，用到n个x
2. 最多只会用到 n + 2m个坐标共3e5个，但范围却有2e9
   即值域跨度很大，需要用到的很少
3. 每一次求区间和，求[l,r]的和，想知道区间内所有的数，进行相加
4. 把所有需要用到的数映射成从1开始的自然数，在它离散化之后的数上加上c即可，若x离散化后的值为k,那就让a[k] += c即可

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;

const int N = 3e5 + 5;

int n,m;
int a[N],s[N];

vector<int> alls;
vector<PII> add,query;

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 r + 1;
}

int main(){
    cin >> n >> m;
    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);
    }
    
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    for(auto item:add){
        int x = find(item.first);
        a[x] += item.second;
    }
    
    //预处理前缀和
    for(int i = 1;i <= alls.size();i++) s[i] = s[i - 1] + a[i];
        
    for(auto item:query){
        int l = find(item.first),r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
   return 0;
}