区间和 - 离散化

比如有序列：

$$1、23、34382627、213934739682$$

假如下标从1开始，让你计算区间$[a[2], a[3]]$的和。这时候数组无法简单做到，因为第二第三的数字远远超过了$10^5$，数组超过了最大的界，因此我们要做离散化。

简单来讲，比如你要有n个插入操作，每次插入提供两个值，一个是插入的位置，一个是插入的值为多少。但插入的位置可能超过$10^5$，这个时候用数组就不能统计区间和了，我们需要对这个数组进行离散化处理：

这里就是在位置1插入2，在位置3插入6，在位置7插入5。然后有三次查询，第一次查询是统计位置1到3的区间和，第二次是4到6，第三次是7到8。

为了创建一个离散化的数组，我们需要先讲插入操作和查询操作用两个数组先保存起来。然后我们定义alls数组，存储这两个操作所涉及到的位置。为了防止alls数组混乱，这个数组不能有重复，而且从小到大排序。为了在之后的操作中，能够找到alls内的位置，我们可以采用二分查找。

alls数组初始化之后，我们可以开始离散化处理了。创建离散化后的数组a，然后：

遍历插入操作的数组，每次寻找插入操作中真实下标的离散化后下标（二分查找得到），然后将离散化下标对应的离散化后数组加上对应的数字。以此类推。

最后查询也是同理，然后利用前缀和就可以了。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PAIR;
const int MAXN = 300010;
int n, m;   //n次插入，m次查询

//  加入队列、查询队列
vector<PAIR> add_query, search_query;
//  离散化时要用到的辅助数组，alls存储着真实下标，alls的自身下标就是离散化后的下标
vector<int> alls;
int a[MAXN], s[MAXN];    //离散化后的数组和对应的前缀和

//寻找x所在的离散化后位置，并返回下标+1，加1是因为我们的下标从1开始（这里是映射过程）
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;
    //n次插入
    for(int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        //  x是真实下标，c是加上的数字
        add_query.emplace_back(x, c);
        alls.push_back(x);
    }
    //m次查询
    for(int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        search_query.emplace_back(l, r);
        //查找的下标也要push进去，不然的话计算前缀和的时候就找不到下标了
        alls.push_back(l);
        alls.push_back(r);
    }
    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    //处理插入，寻找离散化后的下标
    for(auto item : add_query) {
        int x = find(item.first);
        a[x] += item.second;
    }
    //计算前缀和，注意离散化后的数组大小就是alls的，因为alls存储的是真实下标，所以这个数组的大小就是a的数组大小
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    //处理询问，前缀和的做法
    for(auto item : search_query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
}