ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#7088

K번째 수 1s 1024MB

問題

배열 a[1...n]에는 서로 다른 수가 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)이 된다. 정렬한 배열에서 3번째 수는 5이다. 따라서 Q(2,5,3)의 리턴 값은 5이다.

배열 a가 주어지고, Q함수를 호출한 횟수가 주어졌을 때, 각 함수의 리턴 값을 출력하는 프로그램을 작성하시오.


入力

첫째 줄에 배열의 크기 n과 함수 Q를 호출한 횟수 m이 주어진다. (1 ≤ n ≤ 500,000, 1 ≤ m ≤ 5,000)

둘째 줄에는 배열에 포함된 정수가 순서대로 주어진다. 각 정수는 절댓값이 10^9를 넘지 않는 정수이다.

다음 m개 줄에는 Q(i,j,k)를 호출할 때 사용한 인자 i,j,k가 주어진다. (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j-i+1)


出力

Q함수를 호출할 때마다 그 함수의 리턴값을 한 줄에 하나씩 출력한다.


部分問題

番号 点数 条件
#180点

1 ≤ n ≤ 100,000

#220点

例題 

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
5
6
3


出典

NEERC Northern Subregional 2004 K번

ログインしないとコードを書けません。