정렬된 배열에서 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)$: $A_i > K$인 가장 왼쪽 인덱스 $i$ 그러면 $K$의 등장 횟수는 $\text{upper\_bound}(K) - \text{lower\_bound}(K)$이다. 이진 탐색을 두 번 하면 한 질의당 $O(\log N)$. 전체 $O(N + Q \log N)$.