AcWing 802. 区间和
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-13 17:41:18
,
所有人可见
,
阅读 226
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int a[N], s[N];
vector<int> alls; //存放的是所有要来进行离散化的值
vector<PII> adds, query;
//此时来找到x元素在离散化之后的数组的下标
int find(int x) {
int l = 0, r = alls.size() - 1;
while(l < r) {
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
//此时因为考虑到后面使用前缀和数组,所以此时需要将数组元素从下标1开始进行相应的存储
return r + 1;
}
int main() {
int n, m;
cin >> n >> m;
//将需要操作的位置上的数全部读进来
//首先将所有进行插入操作的数读进来
for (int i = 0; i < n; i ++) {
int x, c;
cin >> x >> c;
adds.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());
//下面来完成插入与计算操作, 首先来完成的是插入的操作
for (auto item : adds) {
//首先来找到离散化之后的位置
int x = find(item.first);
a[x] += 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), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}