其他算法

离散化

范围从-N ~ N的坐标轴，其中只有 n 个数被使用(n << N, n 远小于N)

为了减少空间浪费，把坐标离散化，例如：

• 1 -> 0
• 5 -> 1
• 100 -> 2
• 1230 -> 3
• 209093 -> 4
• 25555255 -> 5

这样只需要声明 6 个数组就可以把用到的下标储存完，而不需要开25555256的数组并且有很多空位浪费

实际操作中, 只需要使用一个数据结构把这种对应关系保存下来即可

如果使用数组保存那么可以把离散化后的坐标作为数组下标，原坐标作为值，访问的时候使用二分查找出对应的离散化后的下标

题目

Acwing 802. 区间和

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<pair<int, int>> VII;

VII add, query;
vector<int> alls; // 储存离散化后的下标, 数组的下标是离散化后的下标，储存的值为原来的坐标

const int N = 3e5 + 5;

int s[N];

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; // +1 是为了前缀和方便
}

int main(){
    int n, m;
    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);
    }
    for (int i = 0; i < m; i ++){
        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());

    // add
    for (auto item : add){
        int x = find(item.first);
        s[x] += item.second;
    }

    for (int i = 1; i <= alls.size(); i ++) s[i] += s[i - 1];

    // query
    for (auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}