离散化模板

注意前缀和对于端点0的处理, 故在离散化时返回下标需要 + 1

#include <bits/stdc++.h>
using namespace std;

// 存储所有待离散化的值
vector<int> alls;
vector<int> ans;
vector<pair<int, int>> add;
vector<pair<int, int>> queries;
// 映射
int find (int x) {
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1; // + 1是为了方便前缀和
}

int main () {
    int n, m;
    cin >> n >> m;
    int x, c, l, r;
    // 离散化预处理
    for (int i = 0; i < n; ++i) {
        cin >> x >> c;
        alls.push_back(x);
        add.emplace_back(x, c);
    }
    for (int i = 0; i < m; ++i) {
        cin >> l >> r;
        alls.push_back(l), alls.push_back(r);
        queries.emplace_back(l, r);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    ans.resize(alls.size() + 1, 0);
    // 操作
    for (auto [x, c] : add) {
        ans[find(x)] += c;
    }
    // 前缀和
    for (int i = 1; i < ans.size(); ++i) {
        ans[i] += ans[i - 1];
    }
    // 查询
    for (auto [l, r] : queries) {
        cout << ans[find(r)] - ans[find(l) - 1] << endl;
    }
    return 0;
}