AcWing 802. 区间和(不用离散化,哈希就可以)
原题链接
简单
作者:
虹之间
,
2020-09-25 21:11:53
,
所有人可见
,
阅读 362
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N = 300010;
long long a[N], s[N];
int main()
{
ios::sync_with_stdio(false);
map<int, long long> mp;
int n, m; cin >> n >> m;
for(int i = 0; i < n; i ++ )
{
int index, val; cin >> index >> val;
mp[index] += val;
}
vector<pair<int, int>> query;
for(int i = 0; i < m; i ++ )
{
int index1, index2; cin >> index1 >> index2;
query.push_back({index1, index2});
mp[index1] += 0, mp[index2] += 0;
}
int k = 1;
map<int, int> id; // 存放坐标的映射
for(auto &[index, val] : mp)
{
id[index] = k;
a[k] = val;
s[k] = s[k - 1] + a[k];
k ++ ;
}
for(auto &[l, r] : query)
{
l = id[l], r = id[r];
cout << s[r] - s[l - 1] << endl;
}
return 0;
}