离散化

离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的 全/偏序 关系。

板子

// arr[i] 为初始数组,下标范围为 [1, n]
for (int i = 1; i <= n; ++i)  // step 1
    tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
    arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

例题

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行n次操作，每次操作将某一位置 x 上的数加c。

接下来，进行 m 次询问，每个询问包含两个整数 l和 r，你需要求出在区间 [l,r]之间的所有数的和。

---

一个很简单的思路，先将原始的数组离散化，然后对这个离散化的求前缀和。

#include <bits/stdc++.h>
using namespace std;
int n, m, x;
const int N = 1e6 + 10;
typedef pair<int, int> P;
vector<P> p1, p2;
vector<int> point;
int sum[N], a[N];

int main()
{
    cin>>n>>m;
    
    for(int i = 1; i <= n; i ++)
    {
        int x, c;
        cin>>x>>c;
        p1.push_back({x, c});
        point.push_back(x);
    }
    
    for(int i = 1; i <= m; i ++)
    {
        int l, r;
        cin>>l>>r;
        p2.push_back({l, r});
        point.push_back(l);
        point.push_back(r);
    }
    
    sort(point.begin(), point.end());
    point.erase(unique(point.begin(), point.end()), point.end());
    
    //下面开始找离散后的坐标
    for(auto t : p1)
    {
        int index = lower_bound(point.begin(), point.end(), t.first) - point.begin();
        a[index] += t.second;
    }
    
    //求新的前缀和
    for(int i = 0; i < point.size(); i ++) sum[i] = sum[i-1] + a[i];
    
    for(auto t : p2)
    {
        int l = lower_bound(point.begin(), point.end(), t.first) - point.begin();
        int r = lower_bound(point.begin(), point.end(), t.second) - point.begin();
        cout<<sum[r] - sum[l-1]<<endl;
    }
}