区间和

发布于 18 天前  1 次阅读


#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n, m, arr[N], ans[N];
vector<pair<int, int> > a/*操作*/, q/*询问*/;
vector<int> b;/*边界*/

int find(int x) {//离散化操作(二分)
    int l = 0, r = b.size() - 1, mid;
    while (l < r) {
        mid = l + r >> 1;
        if (b[mid] >= x)r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int x, c;
        scanf("%d%d", &x, &c);
        a.push_back({x, c});
        b.push_back(x);
    }
    for (int i = 1; i <= m; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        q.push_back({l, r});
        b.push_back(l);
        b.push_back(r);
    }
    sort(b.begin(), b.end());//将边界排序
    b.erase(unique(b.begin(), b.end()), b.end());//去重
    for (auto item: a) {
        int x = find(item.first);
        arr[x] += item.second;
    }
    for (int i = 1; i <= b.size(); ++i) {//前缀和,可以用一个数组代替,这里使用了两个数组方便理解
        ans[i] = ans[i - 1] + arr[i];
    }
    for (auto item: q) {//前缀和公式
        printf("%d\n", ans[find(item.second)] - ans[find(item.first) - 1]);
    }
    return 0;
}