题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是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

y总教学视频中的算法

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

using namespace std;

typedef pair<int, int> PII;

const int N=300010;

int n,m;
int a[N],s[N];//离散后

vector<int> alls;//待离散数据
vector<PII> add,query;

vector<int>::iterator unique(vector<int>& alls)
{
    int j = 0;
    for(int i = 0; i < alls.size(); i++)
        if(!i || alls[i] != alls[i-1]) 
            alls[j++] = alls[i];

    return alls.begin() + j;
}
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;
}


int main()
{
    cin>>n>>m;
    while(n--)
    {
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});

        alls.push_back(x);
    }

    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);

        alls.push_back(l);
        alls.push_back(r);

        query.push_back({l,r});
    }
    //排序与去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls),alls.end());

    for (auto item:add)
    {
        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;
}

对代码的一些思考

今天再次写代码时发现可以稍微优化一下空间，只需将需要插入点的坐标进行离散化，对于访问可以不进行离散化，这样就可以把数组开成100010，而不是300010。比如[0,2,4,6,8]这组数据（数据表示坐标轴的位置）如果你需要访问[3,7]之间的数据，只需要将l定位到4元素的位置，而r定位到6元素的位置即可。

实现想法

我写了两个查找函数find1和find2，find1用来查找大于等于x的最小元素（用于查找l，比如刚刚查找3，查找不到将会定位到4元素的位置），而find2用来查找小于等于x的最大元素（用于查找r，比如刚刚查找7，查找不到将会定位到6元素的位置）

调试过程中的问题

存在边界问题还是刚刚的例子比如你需要访问[9,12]之间的元素，查找l过程中会定位到8的位置，同样查找r的过程中也会定位到8的位置。这并不是我们想要的结果。

解决问题

如果发现l>8或者r<0（对于上述例子）直接直接输出。

参考文献

C++ 代码

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

using namespace std;

typedef pair<int, int> PII;

const int N=100010;

int n,m;
int a[N],s[N];//离散后

vector<int> alls;//待离散数据
vector<PII> add,query;

int find1(int x)//查找l
{
    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;
}
int find2(int x)//查找r
{
    int l=0,r=alls.size()-1;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(alls[mid]<=x) l=mid;
        else r=mid-1;
    }
    return r+1;
}


int main()
{
    cin>>n>>m;
    while(n--)
    {
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);
    }

    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
    }

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

    for (auto item:add)
    {
        int x=find1(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)
    {
        if(item.first>alls.back()||item.second<alls.front())//判断是否会出现上述调试的问题
        cout<<0<<endl;
        else
        {
            int l=find1(item.first),r=find2(item.second);
            cout<<s[r]-s[l-1]<<endl;
        }
    }

    return 0;
}

结语

新人一枚，刚刚入门算法，希望记录下一些不成熟的想法。第一次用acwing写题解有些操作还不熟练。