离散化 + 前缀和

$O(nlogn)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int uni[N], s[N], cnt;
int a[N], x[N], c[N];

int n, m, l, r;

void discrete(){
    sort(a, a + n);
    for(int i = 0; i < n; i++){
        if(i == 0 || a[i] != a[i - 1]) uni[++cnt] = a[i];
        }
}

int query_l(int x){
    int l = 1, r = cnt;
    while(l < r){
        int mid = (l + r) >> 1;
        if(uni[mid] >= x) r = mid;
        else l = mid + 1;
        }
    return l;
}

int query_r(int x){
    int l = 1, r = cnt;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(uni[mid] <= x) l = mid;
        else r = mid - 1;
        }
    return l;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d %d", &x[i], &c[i]);
        a[i] = x[i];
        }
    discrete();
    for(int i = 0; i < n; i++){
        int p = query_l(x[i]);
        s[p] += c[i];
        }

    for(int i = 1; i <= cnt; i++) s[i] += s[i - 1];
    for(int i = 0; i < m; i++){
        scanf("%d %d", &l, &r);
        int pl = query_l(l), pr = query_r(r);
        if(pl > pr || l > uni[cnt]) puts("0");
        else printf("%d\n", s[pr] - s[pl - 1]);
        }

    return 0;
}