AcWing 802. 区间和
原题链接
简单
作者:
Value
,
2020-04-28 11:26:31
,
所有人可见
,
阅读 514
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 300010;
int n, q;
int s[N], t[N];
typedef pair<int ,int> pii;
vector<pii> add, query;
vector<int> a;
int find(int x){
int l, r;
l = 0, r = a.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main(){
cin >> n >> q;
int index, tmp;
for(int i = 0; i < n; i ++ ){
scanf("%d%d", &index, &tmp);
add.push_back({index, tmp});
a.push_back(index);
}
int l, r;
for(int i = 0; i < q; i ++ ){
scanf("%d%d", &l, &r);
query.push_back({l, r});
a.push_back(l);
a.push_back(r);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
//初始化r
for(int i = 0; i < add.size(); i ++ ){
index = find(add[i].first);
t[index] += add[i].second;
}
//初始化前缀和s
for(int i = 1; i <= a.size(); i ++ ){
s[i] = s[i-1] + t[i];
}
//查询
for(int i = 0; i < query.size(); i ++ ){
l = find(query[i].first);
r = find(query[i].second);
cout << s[r] - s[l-1] << endl;
}
return 0;
}