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

模板如下:

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。

立志成为一名攻城狮
最后更新于 2020-11-24