구간 k번째 수
플래티넘 IV의견: 0
길이가 \(N\)인 정수 수열 \(A_1, \dots, A_N\)이 주어진다. \(Q\)개의 질의 l r k에 대해
구간 \([l, r]\)의 원소들을 정렬했을 때 \(k\)번째로 작은 값
을 출력한다. 정렬을 매번 하면 시간 초과가 나므로 머지 소트 트리(또는 지속 세그먼트 트리)가 필요하다.
\(1 \le N, Q \le 100{,}000\)
\(1 \le A_i \le 10^9\)
\(1 \le l \le r \le N\), \(1 \le k \le r-l+1\)
첫 줄에 \(N\), \(Q\).
둘째 줄에 \(A_1, \dots, A_N\).
이후 \(Q\)줄에 l r k (\(1 \le k \le r-l+1\)).
각 질의의 답을 한 줄에 하나씩 출력한다.
6 3
4 1 5 2 6 3
1 6 1
1 6 6
2 5 2
1
6
2\([1,6]\) 정렬 시 1,2,3,4,5,6. 1번째=1, 6번째=6. \([?]\) 마지막 질의 \([5,2]\)? 실제로는 2 5 2이며 구간 \([2,5]\)=[1,5,2,6] 정렬 1,2,5,6의 2번째=2.
4 2
7 7 7 7
1 4 1
2 3 2
7
7모두 7. \([1,4]\)의 1번째=7, \([2,3]\)의 2번째=7.
플래티넘 Iriseoj 작성
출처 Original
평가 및 의견
구간 k번째 수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 k번째 수