백준 //선분 위의 점//11663//정렬(Sorting)**과 **이분 탐색(Binary Search)

https://www.acmicpc.net/problem/11663

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> points(n);//1 3 10 20 30
    for (int i = 0; i < n; i++) 
    {
        cin >> points[i];
    }

    vector<pair<int, int>> segments(m);
    for (int i = 0; i < m; i++) 
    {
        cin >> segments[i].first >> segments[i].second;//1 10 ,20 60, 3 30, 2 15, 4 8
    }

    sort(points.begin(), points.end());

    for (int i = 0; i < m; i++) 
    {
        int l = segments[i].first; //1
        int r = segments[i].second; //10
		
        //1부터 30까지의 점(1 3 10 20 30)이 선의 시작점보다 작은면 버리고 그 index 값을 구하기
        int leftIndex = lower_bound(points.begin(), points.end(), l) - points.begin();
        //(1 3 10 20 30)점들 중 선의 끝점보다 크면 버리고 그 index 값을 구하기
        int rightIndex = upper_bound(points.begin(), points.end(), r) - points.begin();

        cout << rightIndex - leftIndex << "\n";
        // 1,10 = 2-0 =2
        //20,60 = 5- 3 =2
        //3 30 = 5-1=4
        //2 15 = 3 -1=2
        //4이상인 첫번째 값(10) - 8보다 큰 첫번째값(10) = 2-2=0
    }

    return 0;
}