Introduction

给定一个整形数组，每个单元的内容的范围非常大，比如$10^9$，也可以看成一个无限长的数轴。但是数组长度（数据的个数）不多，可能只有$10^5$。显然我们那么我们在使用时显然不能依次连续地给所有数值都放在对应下标的数组位置，就需要进行离散化

也可以这么理解：有一个无限长的数轴，大部分位置的数值都是0，只有少部分位置是非零，我们需要求数轴上某个区间上的数值总和。显然大部分为0的位置我们不用进行处理，只需要累加非零数值即可

离散化的结果就是，在新的数组中，每个下标都有意义

小栗子

给定几个整数：1，3，100，2000，500000

我们可以把这几个数分别对应到下标：1，2，3，4，5

注：离散化要保序，即较大的数值可以对应到较大的下标

Question

$$ \begin{align} &假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。\\ &现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c 。\\ &接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。\\ &\textbf{输入格式}\\ &第一行包含两个整数 n 和 m。\\ &接下来 n 行，每行包含两个整数 x 和 c。\\ &再接下来 m 行，每行包含两个整数 l 和 r。\\ &\textbf{输出格式}\\ &共 m 行，每行输出一个询问中所求的区间内数字和。\\ &\textbf{数据范围}\\ &−10^9≤x≤10^9,\\ &1≤n,m≤10^5,\\ &−10^9≤l≤r≤10^9,\\ &−10000≤c≤10000\\ \end{align} $$

输入样例：

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

输出样例：

8
0
5

思路

有意义的下标由两类组成：add操作时，被加位置；query操作时，区间的两个端点——均指原无限长数轴的下标

我们可以把用到的下标存起来，然后进行统一的离散化，映射到新的数组。例如本题中，add操作进行三次，用到了三个有意义的下标：1，3，7；query操作进行三次，用到了六个 有意义的下标：1，3，4，6，7，8。

所以，我们添加了九个待映射的下标。然后进行去重，排序等等操作，即可映射到连续下标

代码实现

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

const int N = 300030;
int a[N], s[N];

typedef pair<int, int> PII;
/* 
    pair容器：一个pair包含两个int变量，为一对
    typedef：相当于给pair<int, int>一个别名叫PII，方便后续使用
*/

vector<int> alls;
// 开设一个vector数组alls，用来存放待离散化的数据，后续再处理
vector<PII> add, query;
/*
    每次add和query都是有两个参数：
    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 r + 1;
}

int main () {
    int n, m;
    scanf("%d%d", &n, &m);
  
    while (n -- ) {
        int x, c;
        scanf("%d%d", &x, &c);
        alls.push_back(x); // 存入alls数组
        add.push_back({x, c}); // 存入add数组
    }
  
    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        alls.push_back(l); 
        alls.push_back(r); // 两个端点存入alls数组
  
        query.push_back({l, r}); // 存入query数组
    }
  
    sort(alls.begin(), alls.end() ); // 将alls数组排序
    alls.erase(unique(alls.begin(), alls.end() ), alls.end() ); // 去重
    // 一定要排序去重之后，才能调用find函数进行映射！！！
    // 这样可以确保下标一一对应！！！

    for (auto item : add ) {
        int x = find(item.first); 
        /*
            遍历add数组，每个元素都是PII。第一个表示被加位置，第二个表示被加数值
            找到x在映射数组a[]中的下标，加上PII.second
        */
        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);
        int r = find(item.second);
        // 遍历query数组，找到查询区间在a[]中的映射下标
        cout << s[r] - s[l - 1] << endl;
        // 输出前缀和
    }
    return 0;
}

补充说明

sort函数

sort(a.begin(), a.end() )
// 对a数组的全部元素进行排序

但是sort函数是不稳定的。

稳定：如果存在两个相同的元素，则不进行交换，不会改变其相对位置

不稳定：即使两个元素相等，也可能交换位置

unique函数和erase函数

unique函数作为C++ stl容器的迭代器，可以起到去掉重复元素的作用

unique函数需要两个参数，分别是去重的起始和结束。根据stl特色，左闭右开，eg：

unique(a.begin(), a.end() )
// 可以对a数组的全部元素进行去重操作
// 因为a.begin()是a[0]，而a.end()是a[n]，n为a数组长度

但是实际上，有两点需要注意：

1. unique函数并非直接将数组元素抹去，而是只进行一个去重的排序，然后返回结束位置。他会把所有重复的元素只留一个放在a.begin()和unique返回值之间（左闭右开），多余的元素放在数组的末尾。所以数组的元素只是被移动了，没有被删除
2. unique的作用对象必须是有序数组。unique只是针对相邻元素进行判重处理，所以在使用unique函数时，需要先进行排序

所以，一般针对有序数组去重，我们组合使用unique和erase函数：

a.erase(unique(a.begin(), a.end() ), a.end() )
// unique返回去重完毕部分后面的一个元素
// erase把去重完毕部分后面所有元素都删除

自写unique

如果一些语言中没有unique迭代器，我们可以根据原理自己写出来

一个有序数组，它的形式应该是：1,1,2,2,2,3,3,3,3,3,666

通过观察可以发现，需要保留的元素必须满足以下两点其中之一：

1. 它是数组中的第一个元素
2. 它与前一个元素不相等

我们把这种元素拉出来就可以了

进行一种双指针算法：i负责从头到尾扫描数组中的所有元素，j负责指向待保存的位置

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];
    }
    // a[0] ~ a[j - 1] 中存放了a中所有不重复的数
    return a.begin() + j;
}

由于j指针绝对不会超过i指针，所以可以直接在a数组中进行操作，不需要另外开数组