AcWing 802. map容器+前缀和+lower_bound二分查找实现区间和
原题链接
简单
# include <iostream>
# include <map>
# include <algorithm>
using namespace std;
# define read(x) scanf("%d", &x)
int n, m;
int x, c;
int l, r;
map<int, int > mp;
int main(){
read(n), read(m);
for (int i = 0; i < n; i ++) read(x), read(c), mp[x] += c;
for (map<int, int>::iterator iter = mp.begin(); iter != mp.end(); ++ iter){
// cout << iter->second << endl;
if (iter != mp.begin()){
map<int, int>::iterator tem = --iter;
iter ++;
iter->second += tem->second;
// cout << iter->second << endl;
}
// cout << iter->second << endl;
}
while (m --){
// int ans = 0;
read(l), read(r);
map<int, int>::iterator iterl = mp.lower_bound(l); // >=
-- iterl;
map<int, int>::iterator iterr = mp.upper_bound(r); // >
-- iterr;
// for (map<int, int>::iterator iter = iterl; iter != iterr; ++ iter){
// ans += iter->second;
// }
// cout << iterl->first <<" " << iterr->first << endl;
cout << iterr->second - iterl->second <<endl;
}
}