离散化

为什么要离散化处理？ 数据过于多时难以表示数组下标 离散化是什么？ 可以类比哈希表

离散化就像哈希一样，只不过是由大映射到小。 比如你有一个长度为1e9数列，其中大部分值都为0，而你要寻找某一区间和，1e9的长度开数组肯定会爆栈，所以我们需要把有效区间缩小至小区间内表示。

离散化例题

ac代码：

#include <bits/stdc++.h>
using ll = long long;
const int N = 3e5 + 9;
std::vector<int> X;
ll a[N];

// 操作和询问
struct Q {
    ll a, b;
} add[N], que[N];

int getindex(ll x) {
    return std::lower_bound(X.begin(), X.end(), x) - X.begin() + 1;
}

void vol() {
    int n, q;
    std::cin >> n >> q;
    // 离线处理
    for (int i = 1; i <= n; i++) {
        ll x, w;
        std::cin >> x >> w;
        X.push_back(x);
        add[i] = {x, w};
    }

    for (int i = 1; i <= q; i++) {
        ll l, r;
        std::cin >> l >> r;
        X.push_back(l), X.push_back(r);
        que[i] = {l, r};
    }
    // 排序去重
    std::sort(X.begin(), X.end());
    X.erase(std::unique(X.begin(), X.end()), X.end());

    for (int i = 1; i <= n; i++) {
        // 由大到小
        int x = getindex(add[i].a);
        ll w = add[i].b;
        a[x] += w;
    }
    // 前缀和
    for (int i = 1; i <= X.size(); i++) {
        a[i] += a[i - 1];
    }

    for (int i = 1; i <= q; i++) {
        int l = getindex(que[i].a);
        int r = getindex(que[i].b);
        std::cout << a[r] - a[l - 1] << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(0), std::cout.tie(0), std::cin.tie(0);
    int t;
    t = 1;
    //std::cin >> t;
    while (t--) {
        vol();
    }
    return 0;
}