题目描述

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

−109≤x≤109
,
1≤n,m≤105
,
−109≤l≤r≤109
,
−10000≤c≤10000

样例

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：

8
0
5

算法1

$O(nlog(n))$

这题要求在对应位置x存储对应值c，而且姑且我们认为位置x为key，而值c为value。
以往我们直接令a[key]=value，再建立前缀和s[i]=s[i-1]+a[i]，就可以很快的求出[l,r]区间和。
但这只适合key比较密集、范围较小的情况，对于离散的情况明显不适合，大部分空间不会用到，而且空间不够。
因此，我们需要将key和value分开存储，这样就可以用较少的空间来连续存储了。
key保存在all_x中，value保存在a中
有几点要确保：
1、key和value之间要保持联系，保证通过key能找到value。
解决措施：我们将key和value保存在不同的数组，但它们的下标一样。
2、我们需要对all_x进行排序和去重，保证key单调和唯一。
3、我们不能再用key进行直接访问了，而应该二分查找，找到key并返回下表x，
这样就可以通过a[x]获取对应的value。

时间复杂度

参考文献

C++ 代码

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

const int N=3e5+10;

typedef pair<int,int> PII;
vector<PII> add,query;
vector<int> all_x;//记录使用过的x,
int a[N],s[N];

int find(int x){

    int l=0,r=all_x.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(all_x[mid]>=x) r=mid;
        else              l=mid+1;
    }
    return r+1;
}
int main(){
    int n,m;
    cin>>n>>m;

    int x,c;
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&c);
        all_x.push_back(x);//存储出现过的x

        add.push_back({x,c});//存储 操作
    }

    int l,r;
    for(int i=0;i<m;i++){
        scanf("%d%d",&l,&r);
        all_x.push_back(l);//存储出现过的x
        all_x.push_back(r);
        query.push_back({l,r});//存储 查询
    }
    //排序并去重
    sort(all_x.begin(),all_x.end());
    all_x.erase(unique(all_x.begin(),all_x.end()),all_x.end());

    for(auto item:add){
        int x=find(item.first);
        a[x]+=item.second;
    }

    for(int i=1;i<=all_x.size();i++) s[i]=s[i-1]+a[i];//前缀和

    for(auto q:query){
        int l=find(q.first);
        int r=find(q.second);

        cout<<s[r]-s[l-1]<<endl;

    }
    return 0;
}