题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

离散化

1. 因为数的范围很大, 但是数很少, 这道题不能直接用前缀和做, 要用离散化将 n 个数映射到 1 - n 的坐标上去.
2. 用 int 数组 alls 来保存所有需要被离散化的数, 包括输入的 n 个数以及 m 次询问的区间左端点 l 和右端点 r , 因此需要开 $3 * n$ 长度的数组.
3. 用 pair<int, int> 数组分别存放 n 次相加操作的 {x, c} 和 m 次询问区间操作的 {l, r}.
4. 在完成输入处理之后, 将 alls 数组排序并去重, 在通过 find 函数找到 n 次相加操作的数组下标.
5. 在完成 n 次相加操作之后, 预处理前缀和.
6. 通过 find 函数找到 m 次询问区间 [l, r] 的下标, 直接通过前缀和求出区间和.
7. find 函数通过二分查找
8. 之前 alls 数组去重中如果要自己实现 unique 函数, 用 i 和 j 双指针, i 遍历数组, 若 i 是第一个元素或第 i 个元素与前一元素不同, 则将 a[i] 赋给 a[j] , 最后记得返回的是迭代器 a.begin() + j .

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l + 1;
}

vector<int>::iterator unique(vector<int> &a) {
    int j = 0;
    for (int i = 0; i < a.size(); i ++ ) {
        if (!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    }

    return a.begin() + j;
}

int main() {
    cin >> n >> m;

    while (n -- ) {
        int x, c;
        cin >> x >> c;
        alls.push_back(x);
        add.push_back({x, c});
    }

    while (m -- ) {
        int l, r;
        cin >> l >> r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l, r});
    }

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls), alls.end());

    for (auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }

    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];

    for (auto item : query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}