题目描述

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

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

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

样例

输入

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

输出

8
0
5

C++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

struct Node //记录下标和加上的值大小
{
    int idx;
    int val;
    bool operator < (Node a)    //用于排序，重载小于号
    {
        return idx < a.idx;
    }

}a[N];

int id[N], s[N];    //获得的编号和前缀和

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i)
        scanf("%d%d", &a[i].idx, &a[i].val);

    sort(a, a + n);     //排序
    for(int i = 0; i < n; ++ i)
        id[i] = a[i].idx;
    int len = unique(id, id + n) - id;  //去重

    for(int i = 0; i < n; ++ i)
    {
        int index = lower_bound(id, id + len, a[i].idx) - id + 1;   //离散化
        s[index] += a[i].val;
    }

    for(int i = 1; i <= len; ++ i)      //得到前缀和
        s[i] += s[i - 1];

    int l, r;
    for(int i = 0; i < m; ++ i)
    {
        scanf("%d%d", &l, &r);
        //得到在映射下新的区间
        int tl = lower_bound(id, id + len, l) - id + 1;
        int tr = lower_bound(id, id + len, r) - id + 1;
        if(id[tr - 1] != r) //可能没有刚好和右区间相等的编号
            --tr;
        printf("%d\n", s[tr] - s[tl - 1]);
    }
    return 0;
}