AcWing 802. 算法基础班--习题--P22 区间和(离散化算法)
原题链接
简单
作者:
初静
,
2021-03-22 11:38:00
,
所有人可见
,
阅读 254
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls; //用来存每个需要待离散化的值
vector<PII> add, query;
// 二分法求x对应的离散化的值
int find(int x) {
// int l = 0, r = alls.size() - 1;
// while (l < r) {
// int mid = l + r >> 1; //容易 写在while() 外面去 !!!
// if (alls[mid] >= x) r = mid; // 容易写成a[mid] >= x !!!
// else l = mid + 1;
// }
// return r + 1;
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++)
{
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++) {
int l, r;
scanf("%d%d", &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());
// 插入操作
for (auto item : add) {
auto x = find(item.first);
a[x] += item.second; // 容易写成find(item.second); !!!
}
// 查询前进行前缀和预处理
for (int i = 1; i <= alls.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;
}
return 0;
}