离散化

离散化代码很长，有些人也觉得它很难。

今天cht就跟大家剖析一下离散化。

一下是我学习离散化的心路历程：
学习前：离散化好难啊。
学习后：真弱。
听到一句yxc的话后：很有感触。
关键问题来了，这句话是啥呢？
没错，就是y总在并查集里说的：

你觉得一个算法难，是因为你的大脑对未知世界的恐惧。——yxc

很有道理对吧（废话）
今天我就帮助大家消除某些人对离散化的恐惧。

一、离散化基本思路与vector

离散化适用于这种题目：
比如一个数组有1e5个元素，但每个元素都很大，比如每个元素的范围都是-1e9~1e9，我们就可以用离散化的思路。
那离散化的思路又是什么呢？(O_o)??
离散化的思路就是把一个很大的数映射到一个小的数。
这就是离散化。
听到这里大家一定都觉得很抽象（水一把抽风：抽象=抽风的大象（抽风养的））
那我们举一个栗子例子。
比如这道题： ACWING.802区间和
本题刚好符合离散化的特性，并且加上我们之前讲过的前缀和的思路。
离散化里很重要的一个部分就是vector（变长数组）。
具体用法如下：

vector<int> q;//初始化vector数组。
q.push_back(3);//在q里插入3。
int x = q.size();//将x设为q的长度。
q.pop_back();//弹出元素

题目详解。

这道题目看似很难，其实只需几步。

一、读入与插入。

将所有信息读入并插入vector数组

二、数组去重。

二行STL：

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

三、处理加法。

离散化思路。

四、预处理前缀和。

利用上期介绍的前缀和模板即可。

五、输出

离散化思路
好接下来我们一步步展示：

第一步初始化与读入。

初始化：

#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, m, a[N], s[N];
vector<int> alls;
vector<pair<int,int>> add, query;
int main()
{

}

读入：

cin >> n >> m;
for(int i = 0; i < n; i ++)
{
    int x,c;
    cin >> x >> c;
    alls.push_back(x);
    add.push_back({x, c});
}
for(int i = 0; i < m; i ++)
{
    int l, r;
    cin >> 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 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;
}

处理加法：

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), r = find(item.second);
    cout << s[r] - s[l - 1] << endl;
}

完整模板:

#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, m, a[N], s[N];
vector<int> alls;
vector<pair<int,int>> 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;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int x,c;
        cin >> x >> c;
        alls.push_back(x);
        add.push_back({x, c});
    }
    for(int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> 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());
    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), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
}

这期的分享就到这里了，戳这里观看全部分享： cht的分享
再见！