题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
思路
显然无法开一个大小为2e9的数组来做的。不过我们先试想用数组做会有哪些问题,很显然大部分数组开的空间没用到,大小为0。如果能用一个小一点数组来存储原来数组中那些有用的值就好啦。也就是说,如果能找到一个从大数组的下标和小数组下表的映射关系就可以解决问题。比如:求大数组a的区间[l, r]的所有数的和就等价于求小数组b的区间[l1, r1]的区间和了。因此可以很自然地想到开两个数组来表示这种一一映射关系,ab[N]表示a到b的映射, ba[N]表示b到a的映射。由于a数组的下标范围很大,所以ab[N]数组也会开的很大。这就很智障,因为又回到最初的问题了。
如果我们不要ab[N]行不行呢?因为ab[N]数组的作用就是给定一个a数组的下标能够迅速找到b数组对应的下标。当然是可以的啦!因为有了ba[N]数组我们就可以知道给定一个b数组的下标就可以知道a数组的下标了,我们可以利用二分查找,只要给定一个a数组的下标就可以找到b数组的下标。也就变相实现了ab[N]数组的功能。下面这个find函数就实现了这个功能。当然,如果要用二分查找,ba[N]数组必须有序的。
//alls相当于ba[N]数组,x是大数组a[N]的下标
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;
}
return r + 1;
}
再看看这道题代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
// a[N]存储大树组的值,s[N]表示前缀和
int n, m;
int a[N], s[N];
//alls存储上文提到的ba[N]数组,表示小数组到大树组的映射关系
//add维护大树组下标和值的关系
//query记录输入的查询
vector<int> alls;
vector<PII> add, query;
//表示上文提到的ab[N]数组,表示大数组到小数组的映射关系
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;
}
return r + 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int x, c;
cin >> x >> c;
add.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});
//为什么要把l, r加入到alls数组(ba[N])呢,因为等会儿find(ab[N])操作的时候还得用, find(l), find(r)
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(), alls.end()); // 排序,方便二分查找
alls.erase(unique(alls), alls.end()); // 去重
// 处理插入
for (auto item : add)
{
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;
}