AcWing802区间和

题目地址：https://www.acwing.com/problem/content/804/

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

−1e9≤x≤1e9
1≤n,m≤1e5
−1e9≤l≤r≤1e9
−10000≤c≤10000

题解：通过观察这道题，我们不难看出这就是一道区间前缀和的问题，但是不同在于这里面的下标的范围比较大，1e9，对于比赛而言不会有这么大的存储空间的，但是我们发现这里最多只有n+2*m个不同的数（在[-1e9,1e9]之间），所以实际只有n+2*m个有效的数字，那么便会显而易见的想到了离散化。但是初始的时候，我只是将n个数字进行离散化，后来的2*m的数字没有离散化，那么在后面的求解的过程中就遇到了一些问题，虽然也能解决，但是就比较麻烦了，醉蛛要的是非常容易出错。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
vector<int>all;
pair<int,int>pa[N];
int n,m,a[N]={0},sum[N]={0};

int find(int x){//找到等于x离散化后的下标，从1开始,1  2  3  ... n 
    int l=0,r=all.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(all[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;
}

int main(){
    cin>>n>>m;
    for(int i=1,x,c;i<=n;i++){
        cin>>x>>c;
        pa[i].first=x;
        pa[i].second=c;
        all.push_back(x);
    } 
    for(int i=n+1;i<=n+m;i++){
        cin>>pa[i].first>>pa[i].second;
        all.push_back(pa[i].first);
        all.push_back(pa[i].second);
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    for(int i=1;i<=n;i++){
        int x=find(pa[i].first);
        a[x]+=pa[i].second;
    }
    for(int i=1;i<=all.size();i++) sum[i]=sum[i-1]+a[i];
    for(int i=n+1;i<=n+m;i++){
        int fx=find(pa[i].first);
        int fy=find(pa[i].second);
        cout<<sum[fy]-sum[fx-1]<<endl;
    }
    return 0;
}

写于：202/8/23  12:56