离散化

原理

见《进阶指南》第32页。

模板题

AcWing-802-区间和

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
vector<PII> add, qry;
const int N = 300010;
int a, b, nums[N];
int arr[N], sum[N];

void discrete () {
    sort(nums + 1, nums + a + 1);
    b = unique(nums + 1, nums + a + 1) - (nums + 1); // 去重，end - begin
}
int query (int val) {
    return lower_bound(nums + 1, nums + b + 1, val) - nums;
}

int main () {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1, idx, val; i <= n; ++ i) {
        scanf("%d%d", &idx, &val);
        add.push_back({ idx, val });
        nums[++ a] = idx;
    }
    while (q --) {
        int l, r;
        scanf("%d%d", &l, &r);
        qry.push_back({ l, r });
        nums[++ a] = l, nums[++ a] = r;
    }

    discrete();
    for (auto e: add) arr[query(e.first)] += e.second;
    for (int i = 1; i <= b; ++ i) sum[i] = sum[i - 1] + arr[i];

    for (auto e: qry) {
        int l = query(e.first), r = query(e.second);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}