一道离散化好题

首先来介绍一下啥是离散化：离散化本质上可以看成是一种哈希 ，其保证数据在哈希以后仍然保持原来的全/偏序关系。通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

模板如下：

vector <int> discrete; // 存储所有待离散化的值
sort(discrete.begin(),  discrete.end()); // 将所有值排序
discrete.erase(unique(discrete.begin(), discrete.end()), discrete.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x)
{
    int l = 0, r = discrete.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (discrete[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

我们以一道例题来具体说明是如何使用的，离散化其实非常简单

根据题目可知，如果不进行离散化，就需要开\(2*10^9\)大小的数组，空间消耗巨大，会直接MLE，而我们使用到的下标仅有\(n + 2 * m\)个 （某一个位置上加入数c，会用到n个下标，询问l、r会用到2 * m个下标）， 而n和m的范围仅为\(10^5\)，可以看出数轴上的数其实是非常稀疏的：

我们以输入样例为例：

直接将下标进行映射

所以解决此题大概的思路是：

step1：首先读入数据，将所有用到的的下标保存到一个vector中，我这里将其命名为discrete，简写为disc，然后对disc进行排序，排序是方便后面进行add或者query时，能快速找到下标被映射到了哪里，排完序后，数组中可能会有重复元素，使用unique对其去重，然后重新整理disc数组。

step2：因为数组是有序的，所以可以直接写一个二分来得到下标被映射到的位置。

step2：离散化安排好之后，就要开始处理add操作了，每次我们首先找到下标被映射到了哪里，然后在里面加上一个数。

step3：构造前缀和序列，然后每次询问一个区间的时候，可以直接使用差分

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
vector <int> discrete;    //离散化向量
vector<PII> add;            
vector<PII> query;
const int N = 300005;
int a[N], s[N];  //数据数组和前缀和数组
int find(int x) {             //看看x被映射到了哪个地方
    int l = 0,  r = discrete.size() - 1; 
    while(l < r) {             //简单的二分查找
        int m = l + r >> 1;
        if(discrete[m] >= x) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return r + 1;          //将数据映射到1,2,3......，如果不加1的话就映射到0,1,2,3...这个根据题目意思来
}
int main(){
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i &lt; n; ++i) {
        int k, c;
        cin >> k >> c;
        add.push_back({k, c});
        discrete.push_back(k);             //将要用到的下标保存到disc数组中
    }
    
    for(int i = 0; i &lt; m; ++i) {             
        int l, r;
        cin >> l >> r;
        query.push_back({l, r}); 
        discrete.push_back(l);             //将要用到的下标保存到disc中
        discrete.push_back(r);
    }
    
    sort(discrete.begin(), discrete.end());     //排序
    discrete.erase(unique(discrete.begin(), discrete.end()), discrete.end());  //去重，其中unique操作：将重复的数扔到向量尾部，然后返回指向重复数字首端的迭代器，我们再将重复的数字erase掉
    
    //处理加操作
    for(auto item : add) {
        int c = find(item.first);   //找到映射的下标
        a[c] += item.second;       //加上一个数
    }
    
    for(int i = 1; i <= discrete.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;
}

排序去重操作：

unique会返回一个迭代器，指向去重后的第一个元素，然后erase从这个元素开始一直删除到end。