7247 : 범위 내 원소 수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정렬된 정수 배열과 $Q$개의 범위 질의 $(L, R)$이 주어질 때, 각 범위에서 $L \le A_i \le R$을 만족하는 원소의 개수를 구하십시오.
Lower Bound와 Upper Bound를 조합하면 $O(\log N)$에 각 질의를 처리할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
Lower Bound와 Upper Bound를 조합하면 $O(\log N)$에 각 질의를 처리할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정렬된 정수 배열의 크기 $N$과 범위 질의 수 $Q$가 주어집니다. ($1 \le N, Q \le 100{,}000$)
둘째 줄에 정렬된 $N$개의 정수가 주어집니다.
셋째 줄부터 $Q$개의 줄에 $L$, $R$이 주어집니다.
둘째 줄에 정렬된 $N$개의 정수가 주어집니다.
셋째 줄부터 $Q$개의 줄에 $L$, $R$이 주어집니다.
출력 설명
각 질의에 대해 $L \le A_i \le R$을 만족하는 원소의 개수를 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8 3
1 2 3 4 5 6 7 8
2 5
1 8
9 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
8
0도움
bisect_left(arr, L)로 시작 위치를, bisect_right(arr, R)로 끝 위치를 구합니다. 두 위치의 차가 범위 내 원소의 수입니다.