문턱을 넘는 수 세기
플래티넘 I의견: 0
길이 \(N\)의 정수 수열 \(A = a_1, a_2, \dots, a_N\)이 주어진다. \(Q\)개의 질의가 주어지며, 각 질의는 세 정수 \(l\), \(r\), \(x\)로 이루어진다.
각 질의에 대해, 구간 \([l, r]\) 안의 원소 중 값이 \(x\)보다 큰 것의 개수를 구하여라.
질의마다 구간을 직접 훑는 \(O(NQ)\) 풀이는 통과할 수 없다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le a_i \le 10^9\)
\(1 \le l \le r \le N\)
\(0 \le x \le 10^9\)
첫 줄에 수열의 길이 \(N\)과 질의 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
이어서 \(Q\)개의 줄에 각 질의 \(l\), \(r\), \(x\)가 주어진다.
각 질의에 대해 구간 \([l, r]\) 안에서 값이 \(x\)보다 큰 원소의 개수를 한 줄에 하나씩 출력한다.
5 3
5 2 8 1 9
1 5 4
2 4 1
3 3 8
3
2
0질의1 [1,5], x=4: 5,8,9가 4보다 크므로 3개. 질의2 [2,4], x=1: 2,8이 1보다 큼 -> 2개. 질의3 [3,3], x=8: 8은 8보다 크지 않으므로 0개.
4 3
1 1 1 1
1 4 0
1 4 1
2 3 1
4
0
0모두 1. x=0이면 4개 모두 큼 -> 4. x=1이면 1보다 큰 것이 없어 0. [2,3]에서도 x=1이면 0개.
riseoj 작성
출처 Original
평가 및 의견
문턱을 넘는 수 세기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
문턱을 넘는 수 세기