题目描述

在原址上完成排序去重以及预处理前缀和

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

using namespace std;

typedef pair<int, int> PII;

int find(vector<PII> &nums, int n, int t){
    int lo = 0, hi = n - 1;
    while(lo < hi){
        int mi = lo + (hi - lo + 1) / 2;
        if(nums[mi].first <= t) lo = mi;
        else hi = mi - 1;
    }
    return lo;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<PII> nums = {{INT32_MIN, 0}}, query;
    for(int i = 0; i < n; ++i){
        int x, c;
        cin >> x >> c;
        nums.push_back({x, c});
    }
    for(int i = 0; i < m; ++i){
        int l, r;
        cin >> l >> r;
        nums.push_back({l, 0}); //将查询的下标也加入数组中，方便查询（y总的这个思路太棒了）
        nums.push_back({r , 0}); 
        query.push_back({l, r});
    }
    //排序
    sort(nums.begin(), nums.end(), [](PII a, PII b){return a.first < b.first;});

    //去重并求前缀和
    int i = 1, j = 1;
    while(j < nums.size()){
        while(nums[++j].first == nums[i].first) nums[i].second += nums[j].second;
        nums[i].second += nums[i - 1].second;
        nums[++i] = nums[j];
    }

    //输出查询结果
    for(auto x : query){
        cout << nums[find(nums, i, x.second)].second - nums[find(nums, i, x.first) - 1].second << endl;
    }
    return 0;
}