题目描述
此题第一次看确实没看懂，所以此处略作分析，为什么要离散化呢，因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实，第二个原因，本文是数轴，要是采用下标的话，可能存在负值，所以也不能，所以有人可能会提出用哈希表，哈希表可以吗？答案也是不可以的，因为哈希表不能像离散化那样缩小数组的空间，导致我们可能需要从-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数组。
剩下的就是已经讲过的了，前缀后算法，本题的难点是理清楚这个映射关系。
算法1
(离散化) O((n+2∗m)log(n+2∗m))O((n+2∗m)log(n+2∗m))
C++ 代码
#include #include #include using namespace std; typedef pair<int, int> PII; const int N = 300010; int a[N], s[N]; int n, m; vector alls; vector 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 r + 1; } vector:: iterator unique(vector &a) { int j = 0; for(int i = 0; i < a.size(); i ++) if(!i || a[i] != a[i - 1]) a[j ++ ] = a[i]; return a.begin() + j; } 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}); 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;
}
