[백준] 11663번 선분 위의 점

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;


int main(){
    fastio;
    int n,m,a; cin>>n>>m;
    vector<int> v;
    for(int i=0; i<n;i++){
        cin>>a;
        v.push_back(a); //점의 좌표
    }
    
    sort(v.begin(), v.end());
    for(int i=0; i<m; i++){
        int a,b; cin>>a>>b;
        long long first = lower_bound(v.begin(), v.end(), a) - v.begin();
        long long second = upper_bound(v.begin(), v.end(), b) - v.begin();
        cout<<second-first<<'\n';
    }
}

 

<풀이>

lower_bound(v.begin(), v.end(), a)

: lower_bound는 정렬된 범위에서 a 이상의 첫 번째 위치를 반환한다. 반환값은 해당 위치의 반복자(iterator) 이다.

upper_bound(v.begin(), v.end(), b)

:upper_bound는 정렬된 범위에서 b보다 큰 값의 첫 번째 위치를 반환한다.

이후

반복자 자체로는 인덱스 값을 제공하지 않기 때문에, 벡터의 시작 위치를 나타내는 반복자 v.begin()을 빼서 인덱스 값을 얻는다.

또한

lower_bound: x 이상 값의 첫 번째 위치 (구간의 시작 위치)

upper_bound: x보다 큰 값의 첫 번째 위치 (구간의 끝 이후 위치)

 

<예시>

v = {1, 3, 3, 5, 7};
a = 3, b = 5;

- lower_bound(v.begin(), v.end(), 3):

3 이상의 첫 번째 값의 위치 → 1 (인덱스 1).

- upper_bound(v.begin(), v.end(), 5):

5보다 큰 첫 번째 값의 위치 → 4 (인덱스 4).