문제
서로다른 정수로 이뤄진 배열 a[1..n]이 주어졌을 때, 질문 Q(i, j, k)을 연속적으로 처리하는 프로그램을 작성하라.
여기서 Q(i, j, k)라는 것은 다음과 같다: a[i...j]의 숫자를 정렬해서 나열하였을 경우의 k번째 숫자는 무엇인가?
예를 들어, a=(1, 5, 2, 6, 3, 7, 4) 라고 하자. Q(2, 5, 3)이 들어왔을 경우 a[2...5]는 (5, 2, 6, 3)이며, 이를 정렬하였을 경우에는 (2, 3, 5, 6)이 된다.
여기서 k는 3이고 우리가 구하고자 하는 3번째 숫자는 5가 된다. 따라서 배열 a에 대한 Q(2, 5, 3)의 답은 5다.
입력
입력의 첫 번째 줄에는 배열 a의 원소의 개수 N과 Q(i, j, k)의 개수 M이 입력된다(1≤N≤100,000, 1≤M≤5,000).
두 번째 줄에는 N개의 서로 다른 정수가 입력되며 이 숫자들의 절대값은 109를 넘지 않는다.
다음의 M개의 줄에는 Q(i, j, k)의 i, j, k가 입력된다. (1≤i≤j≤n, 1≤k≤j-i+1).
출력
Q(i j k)의 질문이 입력된 순서대로 이에 대한 답을 출력한다.
예제
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
5
6
3
출처
Northeastern Europe 2004, Northern Subregion, poj 2104
로그인해야 코드를 작성할 수 있어요.