题目链接: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 }
原文链接: https://www.cnblogs.com/wydxry/p/15790613.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/184887
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!