24443번 - 알고리즘 수업 - 선택 알고리즘 4

문제

오늘도 서준이는 선택 알고리즘 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 규칙 없이 저장된 배열 A가 있다. 최악의 경우 선형 시간 선택 알고리즘으로 배열 A에서 K번째 작은 원소를 찾아서 우리 서준이를 도와주자. 총 Q 개의 쿼리가 주어지고 다음 두 종류의 쿼리를 수행해보자.

• 1 i j k : A_i, A_i+1, ... , A_j에서 k번째 작은 원소를 출력한다.
• 2 i j : A_i와 A_j를 교환한다.

크기가 N인 배열에 대한 최악의 경우 선형 시간 선택 알고리즘 의사 코드는 다음과 같다.

linear_select(A[], p, r, k) { # A[p..r]에서 k번째 작은 원소를 찾는다.
 1) 원소의 총수가 5개 이하이면 k번째 원소를 찾고 알고리즘을 끝낸다.
 2) 전체 원소를 5개씩의 원소를 가진 ⌈n / 5⌉ 개의 그룹으로 나눈다.
 (원소의 총수가 5의 배수가 이니면 이 중 한 그룹은 5개 미만이 된다.)
 3) 각 그룹에서 중앙값(원소가 5개이면 3번째 원소)을 찾는다.
 원소의 총수가 홀수이면 중앙값이 하나이므로 문제가 없고,
 원소의 총수가 짝수이면 두 중앙값 중 임의로 선택한다.
 이렇게 찾은 중앙값들을 m1, m2, ..., m⌈n / 5⌉이라 하자.
 4) m1, m2, ..., m⌈n / 5⌉들의 중앙값 M을 재귀적으로 구한다.
 마찬가지로 원소의 총수가 짝수이면 두 중앙값 중 임의로 선택한다.
 5) M을 기준원소로 삼아 전체 원소를 분할한다. (M보다 작거나 같은 것은 M의 왼쪽에, M보다 큰 것은 M의 오른쪽에 오도록 한다.)
 6) 분할된 두 그룹 중 적합한 쪽을 선택해 단계 1) ~ 6)을 재귀적으로 반복한다.
}

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 쿼리 개수 Q(1 ≤ Q ≤ 10,000)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A₁, A₂, ..., A_N이 주어진다. (1 ≤ A_i ≤ 10⁹)

다음 Q개의 줄에 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ j - i + 1) 1번 쿼리가 1개 이상 주어진다.

출력

1번 쿼리의 결과를 모두 출력한다.

제한

힌트