8. 离散化

即：映射

由于某一问题需要处理的坐标范围太大，超出数组实际的范围：那么

可将这些坐标全部映射成：1,2,3......N

映射方法：

将需要离散化的数据，全部去重+排序

将数据映射成去重排序后在数组中的位置

find函数

用二分来找x在数组中的位置

// 映射：x是原坐标, 返回映射后的新坐标
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (x <= alls[mid])
            r = mid;
        else
            l = mid + 1;
    }
    return l + 1;
}

可以很容易的看出需要映射的是坐标，那么将所有用到的坐标保存

对这些坐标进行”排序+去重”操作

然后再处理两个操作，处理操作的时候就可以用映射后的坐标了

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int n = 300010; // 所有的点是30W，add操作10W，sum操作一次l，r - 20W
int N, M;
int a[n];
vector<int> alls;
vector<PII> add, query;
// 映射：x是原坐标, 返回映射后的新坐标
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (x <= alls[mid])
            r = mid;
        else
            l = mid + 1;
    }
    return l + 1;
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x); // 用到的全部下标
    }
    while (M--)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 排序+去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for (auto &e : add)
        a[find(e.first)] += e.second;
    // 前缀和
    for (int i = 1; i <= alls.size(); i++)
        a[i] += a[i - 1];

    for (auto &e : query)
    {
        int l = find(e.first);
        int r = find(e.second);
        cout << a[r] - a[l - 1] << endl;
    }
    return 0;
}