思路

离散化，适合定义域很广，但是实际上使用的点却很稀疏的题目。
例如本题定义域[-10^9, 10^9], 但是实际上插入数组的点可能就10W个下标，查询最多查20W个下标，也就是说最多使用了30W个下标。
由于定义域过大，无法直接使用数组求前缀和。而离散化的思想就是压缩定义域。将使用到的坐标映射成1~300000中的某一个，使得求前缀和变成可能。

C 代码

#include<stdio.h>
#define N 300010

typedef struct {
    int x;
    int c;
} Pair;

int find(int idx[], int idxLen, int x) {
    int l, r, m;

    l = 0;
    r = idxLen - 1;
    while (l < r) {
        m = (l + r) >> 1;
        if (idx[m] >= x) r = m;
        else l = m + 1;
    }

    // 一定有解
    return r + 1;
}

void quickSort(int a[], int l, int r) {
    int i, j, x, t;
    if (l >= r) {
        return;
    }

    i = l - 1;
    j = r + 1;
    x = a[(l + r) >> 1];
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    quickSort(a, l, j);
    quickSort(a, j + 1, r);
}

// 去重函数，返回不重复元素的个数
int uniq(int a[], int alen) {
    int i = 0;
    for (int j = 0; j < alen; j++) {
        if (j == 0 || a[j] != a[j - 1]) a[i++] = a[j];
    }
    return i;
}

int main() {
    int n, m, x, c, l, r, idx[N], queries[N], s[N] = {0};
    Pair add[N];

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &c);
        add[i].x = x;
        add[i].c = c;
        idx[i] = x;
    }
    for (int i = n; i < n + 2*m; i += 2) {
        scanf("%d%d", &l, &r);
        idx[i] = l;
        idx[i + 1] = r;
        queries[i - n] = l;
        queries[i + 1 - n] = r;
    }

    // 快速排序去重。
    quickSort(idx, 0, n + 2 * m - 1);
    int idxSize = uniq(idx, n + 2 * m);

    // 完成插入元素操作
    for (int i = 0; i < n; i++) {
        int t = find(idx, idxSize, add[i].x);
        s[t] += add[i].c;
    }

    // 求前缀和
    for (int i = 1; i <= idxSize; i++) {
        s[i] = s[i - 1] + s[i];
    }

    // 在前缀和数组完成查询操作
    for (int i = 0; i < 2 * m; i += 2) {
        l = find(idx, idxSize, queries[i]);
        r = find(idx, idxSize, queries[i + 1]);
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}