구간 K번째 수
플래티넘 I의견: 0
길이 \(N\)의 수열 \(A_1, A_2, \dots, A_N\)이 주어진다.
\(Q\)개의 질의가 주어진다. 각 질의는 세 정수 \(l\), \(r\), \(k\)로 이루어지며, \(A_l, A_{l+1}, \dots, A_r\) 중 \(k\)번째로 작은 값을 출력해야 한다.
각 질의를 정렬로 처리하면 시간 안에 들어올 수 없다. 퍼시스턴트 세그먼트 트리를 이용해 각 질의를 \(O(\log N)\)에 처리해야 한다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(-10^9 \le A_i \le 10^9\)
\(1 \le l \le r \le N\)
\(1 \le k \le r-l+1\)
첫 줄에 \(N\)과 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_i\)가 주어진다.
다음 \(Q\)줄에 각 질의 \(l\), \(r\), \(k\)가 주어진다.
각 질의에 대해 구간 내 \(k\)번째로 작은 값을 한 줄에 하나씩 출력한다.
5 4
5 2 8 1 9
1 5 1
1 5 5
2 4 2
3 3 1
1
9
2
8전체 정렬 [1,2,5,8,9]. 1번째=1, 5번째=9. 구간[2,4]=[2,8,1] 정렬 [1,2,8] 2번째=2. 구간[3,3]=[8] 1번째=8.
4 2
7 7 7 7
1 4 3
2 3 1
7
7모든 값이 같으므로 어떤 k번째든 7이다.
플래티넘 IVriseoj 작성
출처 Original
평가 및 의견
구간 K번째 수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 K번째 수