AcWing 802. 区间和, map + pair离散化,不使用二分
原题链接
简单
//
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
typedef long long ll;
using namespace std;
const int N = 300010;
const int Mod = 998244353;
int n, m;
vector<int> alls;
vector<pair<int, int>> add, query;
map <int, int> fd;
int a[N], s[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
int x, c;
cin >> x >> c;
add.push_back({ x, c });
alls.push_back(x);
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
query.push_back({ l,r });
alls.push_back(l), alls.push_back(r);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());//去重复
//所用全部坐标离散化为alls数组了,find函数可以返回真实坐标(x)对应的离散化坐标
for (int i = 0; i < alls.size(); i++) {//
fd[alls[i]] = i;
}
for (auto item : add) {
a[fd[item.first]] += item.second;
}
for (int i = 1; i <= alls.size(); i++) {
s[i] = s[i-1] + a[i-1];
}
for (auto item : query) {
int l = fd[item.first], r = fd[item.second];
cout << s[r + 1] - s[l] << endl;
}
return 0;
}