离散化

运用离散化的情况： 当数据的范围特别大，但是数据的个数特别少时要用到离散化，否则纯暴力会超时；

模板题：Acwing https://www.acwing.com/problem/content/804/

先用vector存入需要离散化的所有数据，然后排序，去重。为什么去重？类比于前缀和，每个下标有且只有一个，所以要去重。

核心代码：

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

模拟一下。

先把这道板子题抄下来：

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

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

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

输入格式

第一行包含两个整数 n">n 和 m">m。

接下来 n">n 行，每行包含两个整数 x">x 和 c">c。

再接下来 m">m 行，每行包含两个整数 l">l 和 r">r。

输出格式

共 m">m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109">10^9≤x≤10^9,
1≤n,m≤105">1≤n,m≤10^5,
−109≤l≤r≤109">?10^9≤l≤r≤10^9,
−10000≤c≤10000">?10000≤c≤10000

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例:

贴上代码+注释：

#include 
#include 
#include 
using namespace std;
const int N = 300010;   // 加上数字的点个数+要求的区间两个端点的个数
int q[N], s[N]; // s是前缀和，q是进行加法操作的数组
typedef pair<int,int>PII;
vector<int>alls;   // 所有数都要离散化
vectorquery, add; // 区间 以及 操作

int find(int x)    // 离散化：实质是 得到add里的第一个数，去其找对应alls里的下标（但由于要求前缀和，所以从1开始）
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(x >= alls[mid]) l = mid;
        else r = mid - 1;
    }
    return l + 1;
}
int main()
{
    int n, m;
    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 t : add)   // 离散化 加法操作
    {
        int x = find(t.first);
        q[x] += t.second;
    }
    
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + q[i];  // 前缀和， 没有经过上一步操作的数组元素为0 很好理解
    
    for(auto t : query)
    {
        int l = find(t.first);
        int r = find(t.second);
        cout << s[r] - s[l-1] << endl;   // 求区间和 
    }
    return 0;
}