离散化（特指的整数）

一：有序的离散化

• 3*10^5是用到的坐标数量
• n次操作，最多用到n个坐标的数
• m次查询最多用到2m个坐标的数，因为一次查询需要访问两个数，总的加起来一共3*10^5，这也是作为离散后数组的大小

思路就是把要求的区间的数放在一个数组中，利用前面的前缀和的思想进行求解。因为l,r的范围是10^9，所以不能直接按照前缀和的方式，开数组不能开出那么大的数组来。

离散化用vector进行
unique() 返回的迭代器作为 text 成员函数 erase() 的第一个参数，而且它会指向被移除的第一个字符。erase() 的第二个参数是 text 的结束迭代器，因此在没有重复元素的新字符串之后的所有字符都会被移除。

auto的作用：C++11中 也拥有了类似的功能：auto 类型推导

• 注意加法的x和查询的l, r全部都可以是负数，也是使用离散化不能直接使用前缀和的原因。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII; // pair可以理解为一种结构体，因为vector不能存储多个值，pair里面有俩属性，first,second
const int N = 3e5 + 10; // 为什么是3，看前面的图文分析
int n, m; // n是加操作次数，m是查询次数
int a[N], s[N];
vector<PII> add, query; // 因为每次加和查询操作都是两个数，输入的时候需要保存
vector<int> alls; // 把上面加操作和查询操作的所有坐标/下标全部存储下来
/*
    已经把所有操作的下标存在了一个alls的vector数组中，当实际进行加的操作，需要对a进行操作，a的下
    标是离散化的，也就是对alls数组二分查找，定位alls找到对应值的下标，这个就是a的下标，返回以后，
    a[x] += c即可。
*/
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() {
    scanf("%d%d", &n, &m);
    // 不所有的操作保存在add的同时，操作过的下表/坐标全部存到alls中，为后面二分准备
    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()); // sort的目的让alls里面的坐标全部从小到大
    alls.erase(unique(alls.begin(), alls.end()), 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);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}