최솟값과 최댓값

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

예제 입력 1

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

예제 출력 1

5 100
38 100
20 81
5 81

세그먼트 트리를 공부하다가 이해는 되는데 구현이 잘 안 되어서 스파스 테이블을 쓰게 되었습니다.

Sparse Table

MAX, MIN, GCD를 O(1)에 쿼리 가능

조건 1. arr에 저장된 값이 변하지 않는다.

조건 2. f(a, b, c) = f(a, (b, c)) = f(f(a, b),c)로 결합 법칙이 성립한다.

배열 arr와 f 쿼리가 위 조건을 만족할 때 쿼리를 O(lgN) 만에 처리할 수 있는 자료 구조

스파스 테이블(Sparse Table)과 세그먼트 트리(Segment Tree)는 범위 쿼리를 처리하기 위한 자료구조입니다. 이 둘은 서로 다른 특성과 사용 사례를 가지고 있습니다. 아래 표는 이 두 자료구조의 주요 차이점을 정리한 것입니다.

class ST:
    def __init__(self, data, func):
        self.n = len(data)
        self.K = math.ceil(math.log2(self.n))
        self.t = [[0] * (self.K + 1) for _ in range(self.n)]
        self.func = func
        self.build(data)

    def build(self, data):
        for i in range(self.n):
            self.t[i][0] = data[i]
        for j in range(1, self.K + 1):
            for i in range(self.n - (1 << j) + 1):
                self.t[i][j] = self.func(self.t[i][j-1], self.t[i + (1 << (j-1))][j-1])

    def qry(self, L, R):
        j = int(math.log2(R - L + 1))
        return self.func(self.t[L][j], self.t[R - (1 << j) + 1][j])

위 코드는 스파스 테이블(Sparse Table)을 구현한 것입니다.

1. **class ST:**이 클래스는 스파스 테이블을 구현합니다.