离散化-区间和:注意find还是按0开始找的
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 300010;
vector<int> all;
vector<pair<int, int>> add, query;
int a[N];
int s[N];
//find为了找到x在all里面的位置,这里1为起始位置,所以返回r+1
int find(int x) {
int l = 0, r = all.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (x <= all[mid]) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
//存入加的数组
for (int i = 1; i <= n; i ++ ) {
int x, c;
scanf("%d%d", &x, &c);
all.push_back(x);
add.push_back({x, c});
}
//存入查询的数组
for (int i = 1; i <= m; i ++ ) {
int l, r;
scanf("%d%d", &l, &r);
all.push_back(l);
all.push_back(r);
query.push_back({l, r});
}
//对all排序、去重
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
//处理加
for (auto item : add) {
int x = find(item.first);
int c = item.second;
a[x] += c;
}
//定义前缀和
for (int i = 1; i <= all.size(); i ++) s[i] = s[i - 1] + a[i];
//处理查询
for (auto item : query) {
int l = find(item.first);
int r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
}