题目描述

blablabla

样例

#include <iostream>
#include <algorithm>
using namespace std;
#include<vector>
typedef pair<int, int> PII;
#define int long long
vector<PII> add,query;
vector<int> alls;
const int N = 1e5 + 10;
int a[N],s[N];
//找第几个
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;

}
signed main()
{
    int n,m;cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        int x,c;cin >> x >> c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i = 1;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;
}
blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla