시간 제한메모리 제한제출정답맞힌 사람정답 비율
3.5 초 (추가 시간 없음) 512 MB186582920.280%

문제

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

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

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

크기가 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의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

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

출력

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

예제 입력 1

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

예제 출력 1

4
5
7

출처