算法1

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;



int main(){
    unordered_map<long long, long long> mp;
    vector<long long> alls;

    auto lambda = [&](long long x, long long c){
        if(mp.find(x) != mp.end()){
            mp[x] += c;
        }else{
            mp[x] = c;
        }
    };
    long long m, n;
    cin >> n >> m;
    alls.reserve(m + n);
    for(int i=0; i<n; i++){
        long long x, c;
        cin >> x >> c;
        lambda(x, c);
        alls.push_back(x);
    }
    vector<pair<long long, long long>> queries;
    queries.reserve(m);
    for(int i=0; i<m; i++){
        long long l, r;
        cin >> l >> r;
        lambda(l, 0);
        lambda(r, 0);
        alls.push_back(l);
        alls.push_back(r);
        queries.push_back({l, r});
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    unordered_map<long long, long long> prefix_sum;
    long long sum = 0;
    for(const auto& key: alls){
        if(prefix_sum.find(key) == prefix_sum.end()){
            prefix_sum[key-1] = sum;
        }
        sum += mp[key];
        prefix_sum[key] = sum;

    }
    for(const auto& pair: queries){
        cout << prefix_sum[pair.second] - prefix_sum[pair.first-1] << endl;
    }


    return 0;
}

算法2

todo