本题暴力做法：

由于开不了那么大的数组，只能用哈希表来存，但是用哈希表来存的话，就不能用前缀和了，因此会超时。

#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 2e5 + 10;

int n,m;
unordered_map<int,int> h;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i ++){
        int x,c;
        scanf("%d%d",&x,&c);
        h[x] += c;
    }
    while(m --){
        int l,r;
        scanf("%d%d",&l,&r);
        int res = 0;
        for(int i = l;i <= r;i ++){
            res += h[i];
        }
        printf("%d\n",res);
    }
    return 0;
}

什么时候要用到离散化？当题目中数据范围很大，并且该数据是以数组的下标存在的，比如本题中数据范围达到了$10^9$，你如果开一个$10^9$大小的数组，那么肯定MLE了。但是呢，题目要用到数据个数很少，如本题中n次操作，n最大为$10^5$，最多需要用到$10^5$个数。m个查询，m最大为$10^5$，因此最多用到$2 \times 10^5$个数。加到一起本题最多也就用到$3 \times 10 ^5$个数。

即：假如真的开$10^9$大小的数组（我只是说假如），那么数组中大部分位置都是空的。

离散化有两种：

1. 保序离散化，即离散化前若$x \lt y$，那么离散化后也要保证$f(x) \lt f(y)$。本题就是要保序离散化的。保序离散化的方式为：将所有要用到的数据全部读入到alls数组中，然后对该数组排序，排序后去重，去重之后，所有要用到的数据就被离散化成了[0,alls.size() - 1]，即原先要用到的数据最小值被离散化成了0，最大值被离散化成了$alls.size() - 1$。即alls[i]这个数据被离散化为了i，但实际应用时，我们可能要使用前缀和数组或者树状数组，因此虽然要用到了数据被离散化成了[0,alls.size() - 1]，实际我们应用时是用的[1,alls.size()]。

这么说好像不太好理解，举个例子，原本我们是想直接开$10^9$的数组a[]的，如果这样的话就会以a[alls[i]]的形式访问下标alls[i]对应的数据a[alls[i]]，但是由于数据范围高达$10^9$，我们开不了那么大的数组，此时我们已经将alls[i]这个数据离散化为了i，这个i是小于$3 \times 10 ^5$的，所以就让i替代alls[i]来担当在数组a[]中的下标。如果要用前缀和数组或者树状数组，那么就让i + 1替代alls[i]来担当在数组a[]中的下标。

那么如何知道某个数它离散化后的值呢？有两种方法：

• 方法一：哈希（也可以理解为反映射）。
  • 将所有要用到的数据全部读入到alls数组中，然后对该数组排序，排序后去重，去重之后（如果使用方法一哈希，而不是方法二二分的话，那么排序去重可以使用set，因为方法二二分需要用到[]操作，set不支持），所有要用到的数据就被离散化成了[0,alls.size() - 1]。这一步操作完之后，可以遍历alls数组，将alls[i]映射到i存到哈希表中，即discrete[alls[i]] = i;。如果要用到前缀和数组或者树状数组，那么是discrete[alls[i]] = i + 1;

• 方法二：二分。

  • 将所有要用到的数据全部读入到alls数组中，然后对该数组排序，排序后去重，去重之后（此处的去重不可以使用set），假设你想知道某个数x它离散化后的值，因为alls[]数组是有序的，因此你可以二分查找x所在的下标i，如果要用到前缀和数组或者树状数组，那么返回i + 1

• 不要求保序离散化，即离散化前若$x \lt y$，那么离散化后$f(x)$和$f(y)$的大小关系没有要求

做法为开个哈希表，每读入一个数为其分配一个唯一的id即可，一般id从0开始，读入一个数后id ++

set + 哈希 写法：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
using namespace std;

const int N = 3e5 + 10;

typedef pair<int,int> PII;

int n,m;
unordered_map<int,int> discrete; // 离散化存反映射用的

// a为存数据的数组，s为其前缀和数组
int a[N],s[N];

// set实现排序去重
set<int> alls; // 存放所有要用到的下标

/*
存放所有的加操作和查询操作
因为必须要把所有要用到的下标都读入后才能做离散化，进而才能去做这些操作
*/
vector<PII> add,query;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i ++){
        int x,c;
        scanf("%d%d",&x,&c);
        alls.insert(x);
        add.push_back({x,c});
    }
    while(m --){
        int l,r;
        scanf("%d%d",&l,&r);
        alls.insert(l);
        alls.insert(r);
        query.push_back({l,r});
    }
    // 此时所有要用到的下标都已经读入了，并且已经排序去重了
    // 存反映射，因为要使用前缀和数组，所以下标要从1开始
    int cnt = 1;
    for(auto x : alls){
        discrete[x] = cnt ++;
    }
    // 进行所有的加操作
    for(int i = 0;i < add.size();i ++){
        int x = add[i].first; // x为没有离散化之前的下标
        int c = add[i].second;
        int discrete_pos = discrete[x]; // discrete_pos为x离散化后的下标
        a[discrete_pos] += c;
    }
    // 求前缀和
    for(int i = 1;i <= alls.size();i ++){
        s[i] = s[i - 1] + a[i];
    }
    // 进行所有的查询操作
    for(int i = 0;i < query.size();i ++){
        int l = query[i].first; // l为没有离散化之前的下标
        int r = query[i].second; // r为没有离散化之前的下标
        int discrete_l_pos = discrete[l]; // discrete_l_pos为l离散化之后的下标
        int discrete_r_pos = discrete[r]; // discrete_r_pos为r离散化之后的下标
        printf("%d\n",s[discrete_r_pos] - s[discrete_l_pos - 1]);
    }
    return 0;
}

vector + 二分 写法：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 3e5 + 10;

typedef pair<int,int> PII;

int n,m;

// a为存数据的数组，s为其前缀和数组
int a[N],s[N];

// 为什么不用set存呢？set不是可以去重吗？因为set不支持[]操作，但是二分要用到[]操作
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; // 因为要使用前缀和数组，所以要加1
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i ++){
        int x,c;
        scanf("%d%d",&x,&c);
        alls.push_back(x);
        add.push_back({x,c});
    }
    while(m --){
        int l,r;
        scanf("%d%d",&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());

    // 也可以自己写去重逻辑
    // int cnt = 0;
    // for(int i = 0;i < alls.size();i ++){
    //     if(i != 0 || alls[i] != alls[i - 1]) alls[cnt ++] = alls[i];
    // }


    // 进行所有的加操作
    for(int i = 0;i < add.size();i ++){
        int x = add[i].first; // x为没有离散化之前的下标
        int c = add[i].second;
        int discrete_pos = find(x); // discrete_pos为x离散化后的下标
        a[discrete_pos] += c;
    }
    // 求前缀和
    for(int i = 1;i <= alls.size();i ++){
        s[i] = s[i - 1] + a[i];
    }
    // 进行所有的查询操作
    for(int i = 0;i < query.size();i ++){
        int l = query[i].first; // l为没有离散化之前的下标
        int r = query[i].second; // r为没有离散化之前的下标
        int discrete_l_pos = find(l); // discrete_l_pos为l离散化之后的下标
        int discrete_r_pos = find(r); // discrete_r_pos为r离散化之后的下标
        printf("%d\n",s[discrete_r_pos] - s[discrete_l_pos - 1]);
    }
    return 0;
}