🔥

문제

농부 존은 N(1 ≤ N ≤ 100,000)개의 건초더미를 일직선 상의 여러 지점에 놓았습니다. 모든 건초더미가 적절하게 놓였는지를 확인하기 위해서 그를 도와 Q (1 ≤ Q ≤ 100,000)개의 질문을 처리해주세요. 각 질문은 일직선 상의 특정 구간에 건초더미가 몇개가 있는지 물어보는 질문입니다.

입력

첫째 줄에 N과 Q가 주어진다.
다음 줄에는 건초더미의 위치를 뜻하는 N개의 서로 다른 정수가 주어진다. 각각의 정수는 0…1,000,000,000사이 범위이다.
그 다음 Q개의 줄에는 각각 두개의 정수 A, B가 주어진다(0 ≤ A ≤ B ≤ 1,000,000,000). 이는 A에서 B구간 사이에 있는 건초더미의 개수를 묻는 질문이다.

출력

Q개의 줄에 각각의 질문에 대하여 해당 구간에 건초더미가 몇개 있는지를 출력한다.

예제 1 입력

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

예제 1 출력

2
2
3
4
1
0

Source

from bisect import bisect_left, bisect_right

N, Q = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
for i in range(Q):
	A, B = map(int, input().split())
	print(bisect_right(arr, B) - bisect_left(arr, A))

참고