（这里特指整数+保序的离散化）

离散化概念：

常用模板：

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)/2;
        if(alls[mid] >= x) r = mid;
        else l = mid+1;
    }
    return r+1;//映射到1 2 3 ...  如果return r则映射到0 1 2 3...
}

实战题目802：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 30010;

int n,m;
int a[N],s[N];//a为处理后的数组，下标对应离散后的值，s存放前缀和
vector<int> alls;//存放待离散的值
vector<PII> add,query;

//用二分查找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 r+1;//映射从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.erasr(unique(alls,begin(),alls.end()),alls.end());//去重

    //处理插入
    for(auto item : add){       //item代指add
        int x = find(item.first);
        a[x] += item.second;
    }

    //预处理前缀和
    for(int i = 1 ; i <= alls.size()-1 ; i ++) s[i] = s[i-1]+a[i];

    //处理询问
    for(auto item : query){
        int l = find(item.fisrt),r = find(item.second);
        cout << s[r]-s[l-1] <<endl;
    }

    return 0 ;
}