题目解释

首先我们要知道我们要映射的是什么：

• 假设只有三个元素需要映射，分别是数轴上的（x1，c1），（x2，c2），（x3，c3）；
• 映射为：（1，c1），（2，c2），（3，c3）；

如图：

从上面很容易看出，我们先需要做：数轴坐标值到a数组下标的映射
然后在将该坐标的所有累加项累加到a数组对应的位置。

那么接下来的问题就是如何将：坐标值————>a数组下标

y总给出了模板：
1. 先将所有坐标值存到一个vector中，然后将其排序；
2. 第二步，去重。

• 去重代码：

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

• 为什么需要去重？
• 因为在这个题目中，对于一个坐标x1，可能会有多次累加的情况，例如给出两组数据：（x1，1），（x1，2）；
• 所以x1可能会出现多次

到此为止，就可以理解y总的代码思路了：
1. 开一个数组存所有的(xk,ck)，在开一个数组存所有的(l,r)
2. 开一个alls数组存所有的坐标x，将alls排序去重后，得到了数轴坐标值与a数组下标的一一对应；
3. 通过find函数，将数轴坐标值的累加项，添加到对应a数组的位置；

• find函数：

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;     //这里加1是因为a数组从1开始存储（为了计算前缀和）
}

y总代码

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

using namespace std;

typedef pair<int,int> PII;

const int N = 300010;
int a[N],s[N];      //a是隐射数组，s是前缀和

vector<int> alls;   //alls用来存储数轴上的坐标
vector<PII> adds,query;     //adds存储坐标(x,c），query存储查询区间(l,r)

int find(int x)     //返回x在隐射到a 的下标为多少
{
    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;         //这里加1是因为a数组从1开始存储（为了计算前缀和）
}

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

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

        alls.push_back(x);
    }

    while(m--)
    {
        int l,r;
        cin >> 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());

    for(auto item:adds)     //将坐标x 的累加项 累加到a数组对应下标处
    {
        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;
}