题目链接：https://www.acwing.com/problem/content/description/804/

思路：

离散化实质是一种映射

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=3e5+10;
 4 typedef pair<int,int> PII;
 5 vector<int> idx;
 6 vector<PII> add,query;
 7 int a[N],d[N];
 8 int n,m;
 9 int find(int x)
10 {
11     int l=0,r=idx.size()-1;
12     while(l<r){
13         int mid=l+r>>1;
14         if(idx[mid]>=x) r=mid;
15         else l=mid+1;
16     }
17     return r+1;
18 }
19 int main()
20 {
21     cin>>n>>m;
22     while(n--){
23         int x,c;
24         cin>>x>>c;
25         idx.push_back(x);
26         add.push_back({x,c});
27     }
28     while(m--){
29         int l,r;
30         cin>>l>>r;
31         query.push_back({l,r});
32         idx.push_back(l);
33         idx.push_back(r);
34     }
35     sort(idx.begin(),idx.end());
36     idx.erase(unique(idx.begin(),idx.end()),idx.end());
37     for(int i=0;i<add.size();i++){
38         int x=find(add[i].first);
39         a[x]+=add[i].second;
40     }
41     for(int i=1;i<=idx.size();i++){
42         d[i]=d[i-1]+a[i];
43     }
44     for(int i=0;i<query.size();i++){
45         int l=find(query[i].first),r=find(query[i].second);
46         cout<<d[r]-d[l-1]<<endl;
47     }
48     return 0;
49 }