一、理解题意
假定有一个无限长的数轴，数轴上每个坐标上的数都是 \(0\)。
现在，我们首先进行 \(n\) 次操作，每次操作将某一位置 \(x\) 上的数加 \(c\)。
接下来，进行 \(m\) 次询问，每个询问包含两个整数 \(l\) 和 \(r\)，你需要求出在区间 \([l,r]\) 之间的所有数的和。
特殊说明一下，\(alls\)数组下标是从\(0\)开始的，而\(a\)数组下标是从\(1\)开始的，\(alls\)数组与\(a\)数组是一一对应的，但是错位对应的，即\(alls[0]->a[1],alls[1]->a[2],....\)
二、解题思路
-
为什么要离散化？
因为空间上不允许开那么大数据范围的数组！本题\(−{10}^9≤x≤10^9\),,两边都加上就是\(2*10^9\),\(c++\)开不到\(3e7\)以上,再大就空间超限了。 -
什么是离散化？
离散化:范围大，但比较稀疏，真正有数的不多，很多地方是空着的（空着的是0）。利用这一特点，把有用的位置“映射”到一个长度可控的范围上。 -
数组大小的确定
既然要映射到一块小的、能装的下的区域内，那么这个区域最大是多大呢？
因为原始数据坐标共\(n\)个，而查询时坐标是\([l,r]\)，一次两个，一共\(m\)次，需要把所有的坐标全部放到\(a\)数组中，上限是：\(n+2*m\),依题意，就是\(3*1e5\) -
离散化模板
//排序+去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
5.关键代码解析
-
变量的含义
vector<int> alls下标的集合，不管是原来录入的哪个下标增加多少值，还是后面的查询某个区间内（左右两个下标），都统统记录到这里。它是最终小映射区域的超集。通过排序+去重，就成为了最终的数据范围。
vector<PII> add哪个下标增加多少值。
vector<PII> query求从哪到哪中间的数字和 -
映射关系的建立（二分思路）
原来一个下标，现在在小的范围内下标是什么呢？怎么能找到现在新的下标呢？
其实，缩小空间后，不变的是数据的顺序，我们只要根据原来下标中的数据值，在有序的新数组中通过二分法查找，就可以找出新的位置，这就是二分法搜索的原理。 -
映射关系的建立（Hash表思路）
既然\(alls\)数组是排序并去重的，那么它肯定是有序的。未来的\(a\)数组，也是按这个序来的，只不过值是“增加的数字”。我们只要记录好 值->绝对位置 的映射关系，就可以作到不用每次都通过二分去搜索知道新位置，直接就能以\(O(1)\)时间复杂度返回绝对位置下标。
三、离散化+二分法
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;//上限，n+2*m+10
int a[N]; //映射后的数组
int s[N]; //a数组的前缀和数组
vector<int> alls; //坐标集合
vector<PII> add; //1、哪个位置，2：加上多少
vector<PII> query;//1、开始点，2:结束点
int n, m;
/**
* 功能：利用二分法查找原索引x的映射后索引值
* 核心思路：原来是第几个是不变的，离散化后还是第几个,建立起了映射关系。
* @param x 原来的索引号
* @return 映射后小数组内的索引号
*/
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;
}
//一定会命中，返回r和l是一样的
return r;
}
int main() {
//加快输入
ios::sync_with_stdio(false);
//输入数据
cin >> n >> m;
//录入原始数据
while (n--) {
int x, c;
cin >> x >> c;
//记录位置与值
add.push_back({x, c});
//将位置记录到alls里
alls.push_back(x);
}
//读入查询范围
int l, r;
while (m--) {
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());
//生成a数组，每次都在映射后的坐标位置将值变大c
for (int i = 0; i < add.size(); i++) {
PII item = add[i];
//find返回的是下标从0开始的位置，这里为了使用前缀和，要求a数据下标从1开始，有1个偏移量
int x = find(item.first) + 1;//映射为小范围的索引值
a[x] += item.second;
}
//预处理前缀和
for (int i = 1; i < N; i++) s[i] = s[i - 1] + a[i];
//处理询问(前缀和应用)
for (int i = 0; i < query.size(); i++) {
PII item = query[i];
//根据原来的位置值，计算出映射后的位置值
l = find(item.first) + 1;
r = find(item.second) + 1;
//利用一维前缀和计算区间和
cout << s[r] - s[l - 1] << endl;
}
return 0;
}