레이팅 미적용설명
길이가 \(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\)).
출력 형식
각 질의의 답을 한 줄에 하나씩 출력한다.
예제 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.
예제 2
입력
4 2
7 7 7 7
1 4 1
2 3 2
출력
7
7설명
모두 7. \([1,4]\)의 1번째=7, \([2,3]\)의 2번째=7.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그