题目描述

离散化！！！

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10 ;

typedef pair<int,int> PII;

vector<PII> op , query;
vector<int> all;

int find(int x)
{
    return lower_bound(all.begin() , all.end() , x) - all.begin() + 1;
    //lower_bound 时间复杂度O（logn）
}

int a[N] , s[N];

int main()
{
    int n , m ;
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++)
    {
        int x , c;
        cin >> x >> c ;
        op.push_back({x , c});
        all.push_back(x);
    }
    for(int i = 1 ; i <= m ; i ++)
    {
        int l , r ;
        cin >> l >> r;
        query.push_back({l , r});
        all.push_back(l);
        all.push_back(r);
    }
    sort(all.begin() , all.end());
    all.erase(unique(all.begin() , all.end()) , all.end());
    for(auto t : op)
    {
        int f = t.first ;
        int s = t.second ;
        a[find(f)] += s ;
    }
    for(int i = 1 ; i <= all.size() ; i ++)  s[i] = s[i-1] + a[i];
    for(auto t : query)
    {
        int ll = find(t.first);
        int rr = find(t.second);
        cout << s[rr] - s[ll - 1] << endl;
    }
}