前言

对这题挺懵逼的，故写个题解，把目前我所理解的记录下来，不然改天又忘了咯！
总之，这是目前我理解的一些东西。

由于当前知识浅薄，若有错误，感谢指正！！！

题目描述

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

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

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

y总讲得很清楚了，这就不再说了！

总体思路

由于数据的范围很大，是2 * 10^9 量级的，但是数据的个数又很小（相比范围来讲），故这题适合采用离散化，我们将坐标轴上需要用到的点（从add操作、query操作中的数据得到）映射到其排序后的下标，再进行操作即可。

我当前理解的总体的思路：第一步：将x映射到k；第二步：a[k] += c，再进行前缀和操作。

手动模拟

我一开始非常懵逼，将样例对应几个vector向量、数组，模拟放入之后，会理解了一些。（一般懵逼）

两个for循环输入数据之后的情况如下：
add ：{ {1, 2}、{3， 6}，{7， 5} }
query :{ {1， 3}， {4， 6}， {7， 8}， {1， 5} }
alls ： { 1， 3， 7， 1,3， 4,6， 7,8， 1,5 }

对于将查询的左右端点l、r放入alls中，我的理解是：
放进去之后，才能利用find操作找到边界。并且如果query中的l、r不等于add中的值，那就是默认值0了，用于找到前缀和的边界。

注意：find函数是用二分找到第一个大于等于x的下标，但是在这里的作用就是找到x的下标。x是必定存在于alls中的，因为我们将query中的l、r也输入到alls中的。

最后

这是我目前的理解，思路并不是很清楚，但是至少有点头绪了，说不定以后能更深刻理解，h。

离散化的概念感觉挺简单的，用起来不简单呐。

代码

//总的思路：
//1. x -> k, a[k] += c; 
//2. 求前缀和
//2020年7月7日16:58:50

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

using namespace std;

typedef pair<int, int> PII;

const int N = 3e5 + 10; //最大情况下：即n + 2 * m个, 数据均不重复

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

int n, m;
int a[N], s[N]; //a存放离散化后的数组，s是a的前缀和数组

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;   
    }   
    //找到第一个 大于等于 x的数的下标
    //此处即找到 等于 x的下标（因为我们将add、query中的x、l、r都放入alls中了，x是肯定存在的）

    return l + 1; 
}

int main()
{
    cin >> n >> m;
    //输入插入操作的数据
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});  //放入add向量中

        alls.push_back(x);      //将要用到的x放入alls向量中
    }
    //输入要查询的数据：l、r
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});    //放入query向量中

        alls.push_back(l);          //将l、r，也是要用到的x，放入alls向量中
        alls.push_back(r);
    }


    //排序、去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    //进行插入操作，得到离散化后的数组. 即值映射到排序后的下标~
    for (int i = 0; i < add.size(); i ++ )
    {
        int x = find(add[i].first);
        a[x] += add[i].second;
    }

    //前缀和预处理。   
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];

    //查询操作，利用前缀和得到区间和
    for (int i = 0; i < query.size(); i ++ )
    {
        int l = find(query[i].first), r = find(query[i].second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}