什么是离散化？

你会这个题 吗？

题目

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

$-10^9\le x\le 10^9$,
$1\le n,m\le 10^5$,
$-10^9\le l\le r\le 10^9$,
$-10000\le c\le 10000$

输入样例：

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

输出样例：

8
0
5

由于这个题目当中的位置（比如 x, l, r）的大小都是10的9次方的级别，开数组是开不了那么大的。

而这些需要用到的位置的个数加起来有 n + 2*m个的，n 和 m 都是10的5次方的级别的。

所以所有的数字都非常的 散 在 坐标轴上，密度非常低。

所以离散化就是将所有需要用到 的坐标挤在一起，中间没有一个空位。

准备阶段：

本题的思路是：

1. 将所有用到的位置坐标存到alls容器，将n次操作的 x 和 c 存到adds容器当中，将m次询问的 l 和 r 存到query 容器当中
2. 将alls 容器内的元素 排序、去重。
3. 将alls容器内的位置映射到 数组a上
4. 遍历 adds 容器内元素 进行 n 次操作
5. 求数组 a 的前缀和数组 放到 数组 s 当中。
6. 遍历 query 容器，进行 m 次查询

操作1：

操作2：

用到sort 和 unique 记得包含头文件

操作3：

对于映射操作我们需要写一个 find 函数，其功能是给一个 alls容器内一个位置，返回一个映射到数组 a 上的一个位置。

这里其实就是 把 alls 容器里的 位置转换成了他们自己的坐标 + 1.

+1的原因是 因为后面要求前缀和，所以 从1开始会方便很多。

操作4：
执行 n 次操作

操作5：

求前缀和数组

操作6：

执行 m 次询问 ，公式 s[ r ] - s[ l - 1 ]

完整代码如下：

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

const int N = 3e5+10;//需要用到位置的数量

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

typedef pair<int, int> PII;//省代码
vector<int> alls;//存储所有位置
vector<PII> adds;//存储n次操作
vector<PII> query;//存储m次询问

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


int main()
{
    //存储
    scanf("%d%d", &n, &m);
    while (n --)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        adds.push_back({x, c});
        alls.push_back(x);//alls 只需要位置
    }
    
    while (m --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    //------------------------
    //排序、去重
    sort(alls.begin(), alls.end());//排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    //去重 unique 可以将重复的数字放到容器的后面并返回第一个
    //            重复的数字的迭代器
    
    
    //------------------------
    //执行 n 次操作
    for (auto seg: adds)
    {
        a[find(seg.first)] += seg.second;//一定注意要find
    }
    
    //求数组 a 的前缀和数组
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
    
    //执行 m 次询问
    for (auto seg: query)
    {
        int l = find(seg.first);
        int r = find(seg.second);
        printf("%d\n", s[r] - s[l-1]);
    }
    
    return 0;
    
}

完