802. 区间和


离散解法

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

using namespace std;

typedef pair<int,int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];//a为alls排序去重好后的值，s为前缀和

vector<int> alls;//alls为存储值
vector<PII> add, query;//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 r + 1;
}



int main(){

    cin >>  n >> m;
    for(int i = 0 ; i < n ; i ++){

        int x, c;
        cin >> x >> c;
        add.push_back({x,c});//存添加得数

        alls.push_back(x);//下标
    }

    for(int i = 0 ; i < m ; i ++){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);//存下标
    }

    //去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),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), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;

}