题目

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

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

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

输入格式

第一行包含两个整数n和m。

接下来 n 行，每行包含两个整数x和c。

再接下里 m 行，每行包含两个整数l和r。

输出格式

共m行，每行输出一个询问中所求的区间内数字和。

数据范围

−10^9 ≤x≤ 10^9,
1 ≤n,m≤ 10^5,
−10^9 ≤ l ≤ r ≤ 10^9,
−10000 ≤ c ≤ 10000

输入样例：

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

输出样例：

1
2
3
8
0
5

解题思路

这道题看起来就感觉好像是赤裸裸的前缀和与差分。但是仔细看会发现，执行的操作不是对区间执行的，也就是说和差分没有关系，就是简单的前缀和。但是 看 x 的取值范围，到了10^9^了，一般数组可是存不下的，会报错。所以这里就要介绍离散化的思想了。

离散化

这道题操作的次数为 n 次，查询次数为 m 次，也就是说实际上被操作的数字，或者说我们需要讨论的数字，最多不超过 n+2m个。这个数组相当于是 3 10^5，相比于x的10^9小得多。所以我们现在就是需要进行离散化操作。

其实实现离散化也很简单，直接先输入时就存x，之后再去除重复的，剩下的数字就是待操作的。之后再遍历一次操作数组，执行操作，最后求前缀和的时候也只是求这个去重数组就行了。查询就是查询前缀和数组。

这相当于是一种映射。举个例子：我们只用：-10000，0，10000， 20000 。四个数字，但是分散得很开，直接存很浪费空间（开-10000～20000个位置来存），我们离散化之后就变成了4个位置。

离散化的方式有两种：

  1. 一种就是和哈希差不多的方式：先排序，然后指定映射下标。

    例如上面的数组，排序后就变成了[0,1,2,3]（因为我给出来的时候就是排好序了的）

    这种处理的伪代码：

    假设是对A数组离散化，C为待排序数组，L为最终映射结果。

    1
    2
    3
    4
    5
    6
    7
    int C[MaxN], L[MaxN];
    ... // 函数中
        memcpy(C, A, sizeof(A));  // 复制 A 数组
        sort(C, C + n); // 排序
        int l = unique(C, C + n) - C; // 去重
        for (int i = 0; i < n; ++i)
            L[i] = lower_bond(C, C+l, A[i]) - C + 1; //查找

  2. 直接去重。（相同元素没必要存两遍）

    像上面的例子，结果就应该为[-10000,0,10000,20000]

    这种处理的伪代码（因为要用到STL函数，所以最好用vector，而不是普通数组）：

    对A数组离散化。

    1
    2
    sort(A.begin(), A.end()); // n 为A的长度
    A.erase(unique(A,begin(), A.end()), A.end());

相关函数解释

后续为可能会发文章专门讲常用的STL函数，这里主要讲unique()和erase()

unique()

它的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。

unique函数的去重过程实际上就是不停的把后面不重复的元素移到前面来，也可以说是用不重复的元素占领重复元素的位置。

函数原型：

1
iterator unique(iterator it_1,iterator it_2);

参数和返回值都是iterator迭代器，可以理解为位置。参数就是带去重的初始位置和结束位置。返回值就是去重后，最后一个不重复元素的位置。

举例：

初始数组：[1，2，3，3，3，4，5，5，6，7，7，8] 注意，使用前一定要先排序好。

去重后数组：[1，2，3，4，5，6，7，8，3，3，5，7]

最终返回的就是 数字8的位置。

erase()

这个函数就是一个删除函数，有一点类似于remove()

它有三种函数原型：

  1. 处理字符串

    1
    string& erase(size_t pos = 0, size_t n);

    例如：str.erase(0,1)删除字符串第一个字符；str.erase(0,3)删除字符串前三个字符。

  2. 处理任意集合

    1
    iterator erase(iterator pos);

    删除pos位置的元素。注意，但传入参数为字符串的时候，它的参数是find(str)。也就是说先查找字符串在远串中的位置，然后再删除。

    例如：str.erase("c")就是把原字符串中的字母c全删除掉；str.erase(str.first()+2)就是把把第三个元素删除掉。

    注意不能直接写数字。

  3. 区间处理任意集合

    1
    iterator erase(iterator it_1, iterator it_2);

    这个很好理解，就是将it_1到it_2之间的元素删除掉。

上述的离散化中就是利用的第3个函数原型，将重复内容删除掉的。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII; // 处理区间问题一般都要用pair

const int N = 3*1e5 + 5;
int n, m, x, c, mid;
int a[N], s[N]; // a数组存放x位置的值，s是前缀和数组
vector<int> all; // 离散化后数组，存放的是需要操作或者查询的x的位置
vector<PII> add, query; // add存放操作的一对，query存放查询的一对

int binary_search(int num) {
    x = 0; c = n; // [ )
    while (x < c) {
        mid = x + ((c - x) >> 1);
        if (all[mid] == num) return mid;
        else if (all[mid] > num) c = mid;
        else x = mid + 1;
    }
    return -1; // 没有找到,返回-1(不可能找不到)
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> x >> c;
        add.push_back({x, c});
        all.push_back(x);
    }
    for (int i = 0; i < m; ++i) {
        cin >> x >> c; // 节约变量，其实该是 l 和 r，左右区间
        query.push_back({x, c});
        all.push_back(x);
        all.push_back(c);
    }
    // 离散化去重
    sort(all.begin(), all.end()); // 排序
    all.erase(unique(all.begin(), all.end()), all.end()); // 去重
    n = all.size(); //后面不用n了,节约变量
    // 处理操作
    for (auto item: add) { // 遍历处理 add
        // 注意这里不能随便直接对item.first插入，因为元素位置改变了，需要去查找离散化后的位置。
        // 离散化后数组是排好序的，所以可以用二分查找来加快查找的速度
        x = binary_search(item.first);
        a[x] += item.second;
    }
    // 处理前缀和
    // for (int i = 1; i <= n; ++i) s[i+1] = s[i] + a[i+1]; // 大家的前缀和都是从下标 1 开始的，我还是习惯 0 开始
    for (int i = 0; i < n; ++i) 
        if (i) s[i] = s[i-1] + a[i];
        else s[i] = a[i];
    // 处理询问
    for (auto item: query) {
        x = binary_search(item.first);
        c = binary_search(item.second);
        cout << s[c] - s[x-1] << endl;
    }
    return 0;
}