代码

#include <stdio.h>
#define N 300010

typedef struct pair
{
    int car;
    int cdr;
} pair;


pair adds[N], queries[N];
int temp[N], a[N], n, m;

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

void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;
    int mid = l + ((r - l) >> 1);
    int x = a[mid], i = l - 1, j = r + 1;
    while (i < j)
    {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j)
        {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    quick_sort(a, l, j);
    quick_sort(a, j+1, r);
}

int uniq(int a[], int len)
{
    int i = 0;
    for (int j = 0; j < len; j++)
    {
        if (!j || a[j] != a[j-1]) a[i++] = a[j];
    }
    return i;
}


int main(void)
{
    // 读取数据
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &temp[i]);
        adds[i].car = temp[i];
        scanf("%d", &adds[i].cdr);
    }

    for (int i = n, j = 0; i < n + m * 2; i+=2)
    {
        scanf("%d%d", &temp[i], &temp[i+1]);
        queries[j].car = temp[i];
        queries[j++].cdr = temp[i+1];
    }

    // 排序去重, 拿到最后长度
    quick_sort(temp, 0, n+m*2-1);
    int end = uniq(temp, n + m * 2);

    // 插入
    for (int i = 0; i < n; i++)
    {
        int x = find(adds[i].car, 0, end - 1);
        a[x] += adds[i].cdr;
    }
    // 前缀和
    for (int i = 1; i <= end; i++) a[i] = a[i-1] + a[i];

    // 输出结果
    for (int i = 0; i < m; i++)
    {
        int l = find(queries[i].car, 0, end-1), r = find(queries[i].cdr, 0, end-1);
        printf("%d\n", a[r] - a[l-1]);
    }
    return 0;

}