1. 아이디어

• 먼저, 아래 코드로 구현한 이 문제의 시간 복잡도는 다음과 같다.

이진 탐색의 시간 복잡도
https://kangworld.tistory.com/65

• 선분의 시작점과 끝점이 좌표상에 있을 경우 해당 index를 return 해주고
• 선분의 시작점과 끝점이 좌표 위에 없을 경우
  • 시작점일 경우 왼쪽 index를 return 해주고
    ex. 아래의 그림에서 2를 찾는다고 했을 때 left의 값인 index 1을 return 해준다.
    (노란색 - reft, 연두색 - right, 갈색 - left와 right이 만나는 지점)
    
  • 끝점일 경우 오른쪽 index를 return 해준다.
    ex. 아래의 그림에서15를 찾는다고 했을 때 right의 값인 index 2을 return 해준다.
    

2. 코드

import sys
input = sys.stdin.readline


def binary_search(v, dir):
    left, right = 0, n-1

    while left <= right:
        mid = (left+right)//2

        if v < a[mid]:
            right = mid-1
        elif v > a[mid]:
            left = mid+1
        else:
            return mid

    if dir == 0:
        return left
    else:
        return right


n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

for _ in range(m):
    s, e = map(int, input().split())
    l, r = binary_search(s, 0), binary_search(e, 1)
    print(r-l+1)

문제 출처

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