并不是科班的学生,在大一之前一直想要学计算机,却阴差阳错没有进到计算机系.
暑假自学c++和算法基础有时也会遇到较难理解的坎,写题解倒是能让我放松下来吸收知识.
言归正传,此题主要用到了离散化和前缀和,至于开数组范围,我认为最好是观察问题所需要的最大询问和添加次数,并在基础上添加一定范围避免RE.

以下给出代码和注释

**//数据或数组的一些准备**
 #include<iostream> 
 #include<vector> 
 #include<algorithm> 
using namespace std;
const int N =300010; 
int n,m;
int a[N],s[N];
typedef pair<int,int> PII; 
vector<int> alls;
vector<PII> add,query;

**//此处用二分寻找原数组离散化后的数组对应的序号 **
----------

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 l+1;
}
****//通过unique函数将出现过的元素和与出现过的元素重复的元素分隔,返回分隔指向的序号****
----------
vector<int>::iterator unique(vector<int> &a){
    int j=0;
    for(int i=0;i<a.size();i++){
        if(!i||a[i]!=a[i-1]) a[j++]=a[i];
    }
    return a.begin()+j;
}

**//读入数据并将x,l,r整理到alls数组**
----------
int main(){
    cin>>n>>m;
    while(n--){
        int x,c;
        cin>>x>>c;
        add.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);
    }
**//alls数组的排序和去重操作**
----------


    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);
        int r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}