题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。
输出格式
共 m 行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
样例
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
我们用map存入坐标,方便处理每个坐标处的加操作。
因为map默认依照first元素进行排序(升序),然后我们从前往后遍历map并将坐标和该处的值分别存下来(此处不需要去重),并计算出前缀和数组b[]。
然后我们通过对每个l, r在坐标数组a[]中查找大于等于他们的第一个数, 得到l,r对应的在数组a[]的下标ll与rr。因为a[rr] >= r, a[ll] >= l,因此当r != a[rr]时,需要将rr减去1,对于l来说,无论l < a[ll] 还是 l == a[ll] , 所计算区间一定是含有a[ll]的,所以用前缀和计算时l需要减一。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define endl '\n'
#define int long long
#define all(v) v.begin(), v.end()
void solve(){
int n, m;
cin >> n >> m;
vector<int> a, b(n + 1, 0);
map<int, int> mp;
for(int i = 0; i < n; ++ i){
int x, c;
cin >> x >> c;
mp[x] += c;
}
int cnt = 1;
for(auto [x, c] : mp){
a.push_back(x);
b[cnt] = b[cnt - 1] + c;
cnt ++;
}
while(m --){
int l, r;
cin >> l >> r;
int ll = lower_bound(all(a), l) - a.begin();
int rr = lower_bound(all(a), r) - a.begin();
if(a[rr] != r)rr --;
ll --;
cout << b[rr + 1] - b[ll + 1] << endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}