【题解】区间和

题目: 区间和

题意:

题意很简单不再赘述。

思路:

• 离散化看起来简单，实际上手写会发现如果思路不清晰很容出问题。
• 这道题首先将要添加的n个数和m个询问分别用pair存到vector中，然后将所有坐标存到vector中，去重后将待插入元素按照vector中映射的位置存到数组a中，并用s数组求前缀和。
• 那么怎么快速找到某个数在vector中映射的位置呢？答案是二分
• 最关键的一点还是理解将所有坐标离散化的含义。
• 比着代码打一遍差不多就理解了hhh

代码:

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

using namespace std;

//尽管题目告诉我们数据范围是1e5,但是我们要离散化所有的坐标，最多会产生n+2m <= 3e5的坐标
const int N=3e5+10;

//typedef是c++中的语法，在编译阶段生效，属于语句，需要在结尾处加分号。而define是c中的语法，在预处理阶段生效
typedef long long ll;
typedef pair<int,int> PII;

int n,m;
int a[N],s[N];//a[i]是离散化后每个坐标对应的值，s[i]中存前缀和方便快速求出给定区间元素之和
vector<int>alls;//将所有坐标离散化后存在vector中
vector<PII>add,query;

int find(int x)
{
    int l=0,r=alls.size()-1;//右边界是所有数离散化后的最大下标
    while(l<r)
    {//找第一个大于等于x的元素离散化后的位置
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else l=mid+1;
    }
    //为了前缀和方便，防止出现边界问题，离散化后从1开始
    return l+1;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
        int x,c;
        scanf("%d%d",&x,&c);
        
        alls.push_back(x);
        add.push_back({x,c});
    }
    for(int i=0;i<m;++i)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        
        alls.push_back(l),alls.push_back(r);
        query.push_back({l,r});
    }
    
    //去重操作，1.排序2.p.erase(unique(p.begin(),p.end())p.end())  
    //unique函数将给定数组中不重复元素放到前面，返回最后一个不重复元素后面的位置
    //p.erase将给定区间的元素删除
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    //插入元素
    //for(int i=0;i<n;++i)a[find(add[i].first)]+=add[i].second;我的写法
    for(auto item:add)
    {
        int x=find(item.first);
        a[x]+=item.second;
    }
    
    //求前缀和 将所有坐标映射到[1,alls.size()]，所以i要<=alls.size()
    for(int i=1;i<=alls.size();++i)s[i]=s[i-1]+a[i];//a[x]+=c
    
    for(auto item:query)
    {
        int l=find(item.first),r=find(item.second);
        printf("%d\n",s[r]-s[l-1]);//前缀和公式
    }
    
    return 0;
}