AcWing 802. 区间和 (set + map + 前缀和)
原题链接
简单
作者:
纸染
,
2021-01-31 14:40:49
,
所有人可见
,
阅读 241
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N], s[N];
vector<pair<int, int> > add, query;
map<int, int> mp;
set<int> st;
int main() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x, c; cin >> x >> c;
add.push_back(make_pair(x, c));
st.insert(x);
}
for (int i = 1; i <= m; i++) {
int l, r; cin >> l >> r;
query.push_back(make_pair(l, r));
st.insert(l), st.insert(r);
}
int cnt = 0;
for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
mp[*it] = ++cnt;
}
for (int i = 0; i < n; i++) {
int x = mp[add[i].first];
a[x] += add[i].second;
}
for (int i = 1; i <= cnt; i++) s[i] = s[i - 1] + a[i];
for (int i = 0; i < query.size(); i++) {
int l = query[i].first, r = query[i].second;
cout << s[mp[r]] - s[mp[l] - 1] << endl;
}
return 0;
}