民间解法

手动去重

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
typedef pair<int, ll> PII;
#define x first
#define y second

PII q[N]; int n, m, l, r;
ll all[N];

int b_sl(int l, int r, int p){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(q[mid].x >= p) r = mid - 1;
        else l = mid;
    }
    return l;
}

int b_sr(int l, int r, int p){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(q[mid].x <= p) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%lld", &q[i].x, &q[i].y);

    sort(q + 1, q + 1 + n);

    int k = 0;
    for(int i = 1; i <= n; ){
        k++;
        int j = i + 1;
        while(j <= n && q[i].x == q[j].x) {
            q[i].y += q[j].y;
            q[j].x = 1e9 + 10;
            j++;
        }
        i = j;
    }

    sort(q + 1, q + 1 + n);

    for(int i = 1; i <= k; i++) all[i] = all[i - 1] + q[i].y;

    while(m--){
        scanf("%d%d", &l, &r);
        int bl = b_sl(1, k, l), br = b_sr(1, k, r);

        ll res = all[br] - all[bl];
        if(q[br].x > r) res -= q[br].y;
        if(q[bl].x >= l) res += q[bl].y;

        printf("%lld\n", res);
    }

    return 0;
}