범위 안 원소 세기
실버 III의견: 0
\(N\)개의 정수로 이루어진 배열이 주어진다. 이어서 \(Q\)개의 질문이 주어지는데, 각 질문은 두 정수 \(L, R\)로 이루어지며 값이 \(L\) 이상 \(R\) 이하인 원소가 배열에 몇 개 있는지를 묻는다.
질문의 수가 많으므로 매 질문마다 배열 전체를 훑는 방법으로는 시간 안에 답할 수 없다.
\(1 \le N, Q \le 100\,000\), 각 원소와 \(L, R\)의 절댓값은 \(10^9\) 이하이다.
첫째 줄에 배열의 크기 \(N\)이 주어진다. 둘째 줄에 \(N\)개의 정수가 공백으로 구분되어 주어진다. 셋째 줄에 질문의 수 \(Q\)가 주어지고, 다음 \(Q\)개의 줄에 각각 두 정수 \(L\)과 \(R\)이 주어진다 (\(L \le R\)).
각 질문에 대해 값이 \([L, R]\) 범위에 드는 원소의 개수를 한 줄에 하나씩 출력한다.
5
1 3 3 5 8
2
3 5
6 100
3
1\([3,5]\) 범위의 원소는 \(3,3,5\)로 \(3\)개, \([6,100]\) 범위는 \(8\)로 \(1\)개이다.
3
-2 0 2
1
-1 1
1\([-1,1]\) 범위의 원소는 \(0\)뿐이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
범위 안 원소 세기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
범위 안 원소 세기