정렬된 배열에서 K의 등장 횟수

문제

오름차순으로 정렬된 정수 배열 $A_0 \le A_1 \le \cdots \le A_{N-1}$이 주어진다. $Q$개의 질의가 들어오며, 각 질의는 한 정수 $K$이다. 배열에서 $K$가 등장하는 횟수를 구하라.

이진 탐색 두 번

배열이 정렬되어 있어서 가능한 풀이이다. lower_bound와 upper_bound 두 함수를 만든다.

• $\text{lower\_bound}(K)$: $A_i \ge K$인 가장 왼쪽 인덱스 $i$
• $\text{upper\_bound}(K)$: 인 가장 왼쪽 인덱스

그러면 $K$의 등장 횟수는 $\text{upper\_bound}(K) - \text{lower\_bound}(K)$이다.

이진 탐색을 두 번 하면 한 질의당 $O(\log N)$. 전체 $O(N + Q \log N)$.

제한

• $1 \le N, Q \le 10^5$
• $-10^9 \le A_i, K \le 10^9$