离散化
思路
此题第一次看确实没看懂，所以此处略作分析，为什么要离散化呢，因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实，第二个原因，本文是数轴，要是采用下标的话，可能存在负值，所以也不能，所以有人可能会提出用哈希表，哈希表可以吗？答案也是不可以的，因为哈希表不能像离散化那样缩小数组的空间，导致我们可能需要从-e9遍历到1e9（此处的含义就是假如我们需要计算1e-9和1e9区间内的值，那我们需要从前到后枚举，无论该值是否存在），因为哈希表不能排序，所以我们一般不能提前知道哪些数轴上的点存在哪些不存在，所以一般是从负的最小值到正的最大值都枚举一遍，时间负责度太高，于是就有了本题的离散化。
离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。
其实映射最大的难点是前后的映射关系，如何能够将不连续的点映射到连续的数组的下标。此处的解决办法就是开辟额外的数组存放原来的数组下标，或者说下标标志，本文是原来上的数轴上的非连续点的横坐标。
此处的做法是是对原来的数轴下标进行排序，再去重，为什么要去重呢，因为本题提前考虑了前缀和的思想，其实很简单，就是我们需要求出的区间内的和的两端断点不一定有元素，提前加如需要求前缀和的两个端点，有利于我们进行二分搜索，其实二分搜索里面我们一般假定有解的，如果没解的话需要特判，所以提前加入了这些元素，从而导致可能出现重复元素。
本文你用于存储这个关系的数组是alls[N];特地说明下，为什么要开300000+10呢，因为我前面说过了提前考虑了前缀和的因素，加上了2*m个点，又因为怕出现数组越界，多加了10。什么时候会用完300000个空间呢，那就是无重复元素，外加n和m都是1e5次方的打下。
下一步就是写提前数轴点对应的映射后的数组的下标的函数课，此题用的是二分，log(n + 2 * m)
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;
}
为什么返回r + 1,这是变相的让映射后的数组从1开始。此处描述映射后的数组下标对应的数值用的是a数组。
剩下的就是已经讲过的了，前缀后算法，本题的难点是理清楚这个映射关系。
实现细节
分析一下y总的代码。
主要分为5大步：
- 读输入。将每次读入的x c push_back()到add中，将每次读入的位置x push_back()到alls中，将每次读入的l r push_back()到query中。
- 排序、去重。
- 通过遍历add，完成在离散化的数组映射到的a数组中进行加上c的操作（用到find函数）。
- 初始化s数组。
- 通过遍历query，完成求区间[l,r]的和。
常见问题
1.为什么要在alls中需要alls.push_back(l);alls.push_back(r);？
因为再求区间和的时候，我们提前分析到可以使用前缀和来做，求前缀和就需要下标l r，如果不加入l r到alls中的话，第5步中遍历时query就没有办法通过输入的l r去访问a或者s。因为find函数就是输入映射前的下标，返回在alls中的下标+1。
举个例子，拿平时的数组来说，下标都是整形，但是如果要求a[1.5]肯定是有错误的，在这里也一样。
2.为什么要排序和去重？
首先要明确find函数的功能，输入一个离散数组的位置（映射前的位置）x返回连续数组的位置+1（映射后的位置+1）。+1的目的是为了求区间和时少一步下标为0的判断。
排序很好理解，因为在find函数中是使用了二分来查找x在alls中的下标+1，想要使用二分alls就必须具有某种性质这里就可以找一个最简单的办法使他单调（但是y总说过二分!=单调性）
AC代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
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 l + 1;
}
int main()
{
cin >> n >> m;
// 处理添加
while (n -- )
{
int x, c;
cin >> x >> c;
alls.push_back(x);
add.push_back({x, c});
}
//处理查询
while (m -- )
{
int l, r;
cin >> l >> r;
alls.push_back(l), alls.push_back(r);
query.push_back({l, r});
}
// 排序和去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 处理插入
for(auto item : add)
{
// 寻找映射后位置插入点p
int p = find(item.first);
a[p] += 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;
}
