The prefix and discretization

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的第一个元素的位置,如果
//The element was not found in the array or container,then returns the position if the element existed;
//upper_bound(beg,end,val):返回大于val的第一个元素的位置

//uniqueReturns the position of the last element without repeating elements

第一种解法：

//lower_bound(beg,end,val);返回大于等于val的第一个元素的位置,如果
//The element was not found in the array or container,then returns the position if the element existed;
//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}); //Save the incremental information of the coordinates
        all.push_back(x);  //Save the coordinates in all中
    }
    
    while (m -- )
    {
        int l,r;
        cin >> l >> r;
        query.push_back({l,r}); //Save the query information
        all.push_back(l); //Record the information subscript of the query
        all.push_back(r);
    }
    
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end())+1,all.end());//deduplicate the coordinates
    //uniqueReturns the position of the last element without repeating elements
    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;
}

第二种解法：

/**
 * 分析,We can use discretization to solve the prefix sum;
*/

#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; //allAll coordinates representing the increment of the coordinates;
                        //uniqueNon-repeating coordinates representing increments of coordinates;
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,Because the subscript of the prefix sum is from1开始;
}

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,
 * to get the correct subscript
 * */
        cout << s[r-1]-s[l-1] << endl;
    }
    return 0;
    
}