题目分析

本题的目的是实现离散化，降低消耗
因此在这里可以考虑使用map<int,int> mp来存储数据值及其位置，从而实现了自动排序与去重,然后再将该mp存入vector<node>,使用find函数完成对边界l,r的查找工作,最终利用前缀和计算出区间和

相应代码如下

利用map直接实现去重与排序

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

map<int,int> mp;

struct node{
    int val;
    int pos;
    node(int v,int p){
        val=v;
        pos=p;
    }
};

vector<node> A;

//寻找第一个大于等于p的位置
int bfind(int p){
    int left=0;
    int right=A.size()-1;
    while(left<right){
        int mid=(left+right)/2;
        if(A[mid].pos>=p) right=mid;
        else left=mid+1;
    }
    return left;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int x,c;
        cin>>x>>c;
        mp[x]+=c;
    }

    int l[100010];
    int r[100010];
    for(int i=0;i<m;i++){
        cin>>l[i]>>r[i];
        mp[l[i]]+=0;
        mp[r[i]]+=0;
    }

    for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
        A.push_back(node(it->second,it->first)) ;       
    }

    int sum[300010];
    sum[0]=A[0].val;
    int len=A.size();
    for(int i=1;i<len;i++){
        sum[i]=sum[i-1]+A[i].val;
    }

    for(int i=0;i<m;i++){
        int nl=bfind(l[i]);
        int nr=bfind(r[i]);
        if(l==0) cout<<sum[nr]<<endl;
        else cout<<sum[nr]-sum[nl-1]<<endl;
    }

    return 0;
}