用map,vector感觉十分的优雅。
就是把按数字大小排序放到vector里面,查询的时候二分找一下边界,累加这个区间的值,累加的话用前缀和去维护。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int r[N];
int pre[N];
int main() {
int n, m;
cin >> n >> m;
map<int, int>mp;
for (int i = 1; i <= n; i++) {
int x, c;
cin >> x >> c;
mp[x] += c;
}
vector<pair<int, int>>v(mp.begin(), mp.end());
vector<int>pre(v.size() + 1);// [l,r] pre[r+1]-pre[l]
int le = v.size();
for (int i = 1; i <= v.size(); i++) {
pre[i] = pre[i - 1] + v[i - 1].second;
}
while (m--) {
int l, r;
cin >> l >> r; //[q,p] q>=l p<=r
//查询左
int left = -1, right = -1;
int q = 0, p = le - 1;
while (q < p) {
int mid = q + p >> 1;
if (v[mid].first >= l) {
p = mid;
}
else {
q = mid + 1;
}
}
if (v[q].first >= l && v[q].first <= r)left = q;
//查询右
q = 0, p = le - 1;
while (q < p) {
int mid = q + p + 1 >> 1;
if (v[mid].first <=r)q = mid;
else p = mid - 1;
}
if (v[q].first >= l && v[q].first <= r)right = q;
//实际上下标是唯一的 所以可以写成函数
if (left != -1) {
cout << pre[right + 1] - pre[left] << endl;
}
else {
cout << "0" << endl;
}
}
}