杂项积累

迭代器(Iterator)

排序

二分

头文件#include<algorithm>

返回值：迭代器（找不到的时候返回last）

区间[first,last)必须预先有序（升序）

时间复杂度 \(O(log n)\)

lower_bound(v.begin(),v.end(),value) 第一个 \(\geqslant value\) 的迭代器

upper_bound(v.begin(),v.end(),value) 第一个 \(>value\) 的迭代器

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void solve(){
    int n,q;
    cin >> n >> q;
    vector<int> v;

    for(int i = 0;i<n;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    for(int i = 0;i<q;i++){
        int p;
        cin >> p;
        auto l = lower_bound(v.begin(),v.end(),p); // 存在则返回>=val，否则返回
        auto r = upper_bound(v.begin(),v.end(),p); // 返回第一个>val

        if(l!=v.end() && *l==p){
            cout << l-v.begin() << " " << r-1-v.begin() << endl;
        }else {
            cout << -1 << " " << -1 << endl;
        }
    }
}
int main(){
    solve();
    return 0;
}