【2021.2.13】区间和(离散化+前缀和)
知识点:
离散化主要处理当数据范围非常大,但使用到的数非常少(亦即非常稀疏)的情况下区间求和可通过使用前缀和算法来求任意区间范围内的求和,但由于区间范围非常大,因此需要使用离散化技巧
主要思路:
- 首先将所有可能的区间记录下来(包括n次操作和m次询问时所涉及到的下标),并记录开始的n次操作每个原始下标x和c的值
- 其次将所有原始下标进行排序和去重。因此得到新的升序的元素序列,此时将该序列的每个下标作为映射的新的下标,例如:原始输入的下标排序去重后为[1, 2, 100, 10000],则其映射关系为1->0,2->1,100->2,10000->3。实现了较大下标的离散化
- 对于所有的操作或者查询,都可以将原始的下标映射到新的离散化的下标,可以使用hash(map数据结构),也可以使用二分做搜索(因为是有序的序列,所以可以用二分进行查询)
- 最后,使用前缀和算法
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e5 + 5;
int n, m;
int A[N]; // 用于前缀和
vector<int> alls; // 用于记录所有的原始下标
vector<pair<int, int>> v; // 用于记录原始下标及对应新增的值
vector<pair<int, int>> query; // 用于记录query操作的原始下标
int find(int x) {
// 二分法寻找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;
}
return r + 1;
}
int main() {
int x, c, l, r;
// 保存所有的操作数
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) {
scanf("%d%d", &x, &c);
v.push_back({x, c});
alls.push_back(x);
}
for(int i = 0; i < m; i ++) {
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());
// 对add操作进行处理
for(int i = 0; i < v.size(); i ++) {
int new_x = find(v[i].first);
A[new_x] += v[i].second;
}
// 求前缀和
// alls.size()表示所有下标去重后的个数,恰巧对应新映射坐标的个数
for(int i = 1; i <= alls.size(); i ++) A[i] += A[i - 1];
//处理查询
for(int i = 0; i < query.size(); i ++) {
int new_l = find(query[i].first);
int new_r = find(query[i].second);
printf("%d\n", A[new_r] - A[new_l - 1]);
}
return 0;
}
排序+去重的模板:
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());