离散化

离散化处理的问题：
下标范围有负数，或者下标范围超过1e6以上(否则可以直接用数组进行前缀和)，
并且题目还要求按照下标的顺序做题，
离散化结果：将用到的下标全部处理到 0 ~ n，缩小范围后后可以使用前缀和进行求解

离散化算法模板

int find(int x){//将x转化为离散化后的下标，根据离散化后的数组vector<下标,原来的值x>
                //通过二分查找来比对出相等的值从而转化为相应的l~r之间的下标（因为我们将add、query中的x、l、r//都放入alls中了，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;//根据题目要求，下标从1~n,或者0~n
}

思路

alls数组：alls数组存储的是插入的原始下标x及查询操作区间的左右端点的l, r下标
add数组：存储一个二元组pair，存储需要插入的位置以及值
query数组：存储要查询的区间左右端点l, r

模拟一下：
add ：{ {1, 2}、{3， 6}，{7， 5} }
query :{ {1， 3}， {4， 6}， {7， 8}， {1， 5} }
alls ： { 1， 3， 7， 1,3， 4,6， 7,8， 1,5 }

对于将查询的左右端点l、r放入alls中，我的理解是：
放进去之后，才能利用find操作找到边界。并且如果query中的l、r不等于add中的值，那就是默认值0了，用于找到前缀和的边界

几个小问题

去重

会发现其实去不去重都是对的！
- 去重可以减少a数组的占用，即减少0的位置，（对于x, l, r）会发现他们可能会有重复）
- 对于二分alls数组时，可以少循环几次，提高效率

我们二分条件alls[mid] >= x, r = mid，会发现最终二分得到的答案是第一个等于x的位置，对于a数组的计算毫无影响！

时间复杂度

快排：O((n+2m)log(n+2m))O((n+2m)log(n+2m))
去重：O(n+2m)O(n+2m)
二分：O(log(n+2m))O(log(n+2m))，n + 2m 次二分，为O((n+2m)log(n+2m))O((n+2m)log(n+2m))
前缀和：O(n+2m)O(n+2m)
总复杂度为：O((n+2m)log(n+2m))

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 3e5 + 10;//最大情况下：即n + 2 * m个, 数据均不重复

int n, m,
int a[N];
int s[N];//a存放离散化后的数组，s是a的前缀和数组

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 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});//将add操作位置及相应的值加入
        alls.push_back(x);//将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);//将l,r放入alls
    }
    //排序和去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    //离散化到a数组
    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;//离散化后的位置上add相应值
    }
    //求a数组前缀和
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    //查询操作，利用前缀和得到区间和
    for(auto x : query){
        int l = find(x.first), r = find(x.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}