2025-01-25离散化

离散化

主要内容

模板代码

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=alls.size()-1;
    while(l<r){
		int mid=l+r>>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l+1;//下标从1开始
}

例题

区间和

Acwing基础算法 802. 区间和_acwing 802. 区间和-CSDN博客

// https://blog.csdn.net/2301_80072871/article/details/140408415
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;

const int N=3e5+5;
int a[N],sum[N];
int n,m;
vector<PII> add;
vector<PII> query;
vector<int> alls;


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;//[l,mid]
        else l=mid+1;
    }

    return l+1;//因为涉及前缀和，所以映射下标从1开始
}


void work(){
    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) a[find(item.first)]+=item.second;

    for(int i=1;i<=alls.size();i++) sum[i]=sum[i-1]+a[i];

    for(auto item:query) cout<<sum[find(item.second)]-sum[find(item.first)-1]<<endl;
}

int main(){
    work();
    return 0;
}