구간에서 k번째로 작은 값
플래티넘 IV의견: 0
길이 \(n\) 인 정수 배열 \(a_1, a_2, \dots, a_n\) 이 주어진다. 이어서 \(q\) 개의 질의가 주어지며, 각 질의는 세 정수 \(l, r, k\) 로 이루어진다.
각 질의에 대하여, 구간 \(a_l, a_{l+1}, \dots, a_r\) 의 값들을 오름차순으로 정렬했을 때 \(k\) 번째에 오는 값, 즉 그 구간에서 \(k\) 번째로 작은 값을 구하여라. 같은 값이 여러 개 있으면 각각을 따로 센다.
모든 질의가 미리 주어지므로 머지 소트 트리(답에 대한 이분 탐색)나 Mo's 알고리즘으로 오프라인 처리할 수 있다.
\(1 \le n, q \le 10^5\)
\(-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_1, \dots, a_n\) 이 주어진다.
다음 \(q\) 개의 줄에 각각 세 정수 \(l, r, k\) 가 주어진다 (\(1 \le l \le r \le n\), \(1 \le k \le r - l + 1\)).
각 질의에 대한 \(k\) 번째로 작은 값을 입력 순서대로 한 줄에 하나씩 출력한다.
8 4
3 1 4 1 5 9 2 6
1 8 1
1 8 8
3 6 2
1 4 3
1
9
4
3
\(a_{1..8}\) 를 정렬하면 \([1,1,2,3,4,5,6,9]\) 이므로 가장 작은 값은 \(1\), \(8\)번째(가장 큰) 값은 \(9\). \(a_{3..6}=[4,1,5,9]\) 정렬 시 \([1,4,5,9]\) 의 \(2\)번째는 \(4\). \(a_{1..4}=[3,1,4,1]\) 정렬 시 \([1,1,3,4]\) 의 \(3\)번째는 \(3\).
1 1
42
1 1 1
42
원소가 하나뿐이므로 그 구간의 \(1\)번째로 작은 값은 \(42\).
riseoj 작성
출처 Original
평가 및 의견
구간에서 k번째로 작은 값
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간에서 k번째로 작은 값