离散化求前缀和

802. 区间和

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

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

 //lower_bound(beg，end，val);返回大于等于val的第一个元素的位置，如果
//数组或容器内没有查找到该元素，则返回假设该元素存在时的位置；
//upper_bound(beg,end,val):返回大于val的第一个元素的位置

//unique返回不重复元素的最后一个元素的位置

第一种解法：

//lower_bound(beg，end，val);返回大于等于val的第一个元素的位置，如果
//数组或容器内没有查找到该元素，则返回假设该元素存在时的位置；
//upper_bound(beg,end,val):返回大于val的第一个元素的位置
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
vector<PII> add,query;
vector<int> all;

const int N = 3e5+10;
int a[N],s[N];

int main()
{
    int n,m;
    cin >> n >> m;
    while(n--)
    {
        int x,c;
        cin >> x >> c;
        add.push_back({x,c}); //将坐标的增量信息保存下来
        all.push_back(x);  //将坐标保存在all中
    }
    
    while (m -- )
    {
        int l,r;
        cin >> l >> r;
        query.push_back({l,r}); //将查询信息保存下来
        all.push_back(l); //将查询的信息下标记录下来
        all.push_back(r);
    }
    
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end())+1,all.end());//将坐标去重
    //unique返回不重复元素的最后一个元素的位置
    for(auto item:add)
    {
        int id=lower_bound(all.begin(),all.end(),item.first)-all.begin()+1;
        a[id]+=item.second;
    }
    
    for(int i=1;i<=all.size()+1;++i)
        s[i]=s[i-1]+a[i];
        
    for(auto que:query)
    {
        int l=lower_bound(all.begin(),all.end(),que.first)-all.begin()+1;
        int r=lower_bound(all.begin(),all.end(),que.second)-all.begin()+1;
        cout << s[r]-s[l-1] << endl;
    }
    
    return 0;
}

第二种解法：

/**
 * 分析，我们可以用离散化来求解前缀和；
*/

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

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5+10;
int s[N]={0},a[N]={0};

vector<PII> add; //坐标的增量
vector<int> all,Unique; //all表示坐标的增量的所有的坐标；
                        //unique表示坐标的增量的不重复的坐标；
int upper_equal(int val) //返回大于等于val的第一个坐标
{
    int l=0,r=Unique.size(); //r应该设置为unique.size()；
    while(l<r)
    {
        int mid=(l+r)/2;
        if(Unique[mid]>=val)
            r=mid;
        else
            l=mid+1;
    }
    return l+1; //返回l+1，因为前缀和的下标是从1开始；
}

int main()
{
    int n,m;
    cin >> n >> m;
    int x,c;
    for(int i=1;i<=n;++i)
    {
        cin >> x >> c;
        add.push_back({x,c});
        all.push_back(x);
    }
    
    sort(all.begin(),all.end()); 
    for(int i=0;i<all.size();++i)
    {
        if(i==0||all[i]!=all[i-1])
            Unique.push_back(all[i]);
    }
    
    for(int i=0;i<add.size();++i)
    {
        int r=upper_equal(add[i].first);
        a[r]+=add[i].second;
    }
    
    for(int i=1;i<=n;++i)
        s[i]=s[i-1]+a[i];
    
    while(m--)
    {
        int l,r;
        cin >> l >> r;
        l=upper_equal(l);
        r=upper_equal(r+1);
/**不管r在不在unique数组中，  我们返回r+1的坐标，再减去1，
 * 就能得到正确的下标
 * */
        cout << s[r-1]-s[l-1] << endl;
    }
    return 0;
    
}