C++ 离散化求区间和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
整数离散化:就是把范围很大,但是个数比较少的数列,全部映射到一个从0开始的自然数列中
一个数列的,数值范围大,但是数比较少。当需要把这些数当作下标时,由于范围大,
开辟一个大数组不太现实,所以需要离散化。把这个数列映射到由0开始的自然数。
例如: a[] 1 3 100 2000 50000
映射 0 1 2 3 4
离散化两个问题
1.a[]中可能有重复元素,要去重 sort(a.begin(), a.end);
a.erase(unique(a.begin, a.end), a.end)
unique() 去重,重复放后面,返回最后下标
erase() 去掉区间内的元素
2.如何算出x,离散后在a[]中的下标 二分
*/
typedef pair<int, int> PII; // 插入数列 查询
const int N = 300010; // 一次插入数列x 一次查询 [l, r] 3e5
int n, m;
int a[N], s[N];
vector<int> alls; // 存所有要离散化的值,排序去重后,alls的下标与原a的下标对应
vector<PII> add, query; // 插入 查询
// 二分
int find(int x) { // 由原坐标 找到 有映射之后的坐标 某数映射之后的坐标是在alls中,该数的下标
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() {
scanf("%d %d", &n , &m); // n插入个数 m查询次数
for(int i = 0; i < n; i ++) {
int x, c;
scanf("%d %d", &x, &c); // 插入下标以及对应值
add.push_back({x, c}); // 把插入操作加入到add中,以后插入时使用
alls.push_back(x); // 把插入的下标加入到alls中
}
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);
}
// alls 去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (auto item : add) { // 执行插入操作
int x= find(item.first); // 第一个数时插入的坐标
a[x] += item.second; // 第二个数是要插入的数 a[] 从1开始存放插入的数
}
// 预处理前缀和
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); // 找到区间对应的端点
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
小伙不错,继续加油