문제

출처 : https://www.algospot.com/judge/problem/read/MORDOR

모르도르 지방의 아름다운 경치를 한 눈에 볼 수 있는 명산 오로드루인에는 길기로 유명한 등산로가 있습니다. 이 등산로는 산등성이를 따라 오르락내리락하며 구성되어 있지요. 이 등산로는 너무 길기 때문에 특수 장비(예를 들면, 절대반지 등)를 갖춘 사람이 아니라면 처음부터 끝까지 정복하기가 힘이 듭니다. 관광 자원 개척을 위해 이 등산로 중 몇 군데를 별도의 등산로로 개방하려고 합니다.

등산로에는 100미터 간격으로 표지판이 있는데, 각 표지판의 해발 고도를 측정한 자료가 있습니다. 이 때 등산로의 난이도는 등산로를 가다 만나는 표지판 중 최대 해발 고도와 최저 해발 고도의 차이입니다. 개방을 검토하고 있는 등산로의 일부가 주어질 때, 각 부분의 난이도를 계산하는 프로그램을 작성하세요.

입력

첫 줄에는 테스트 케이스의 수 C (1 <= C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 원래 등산로에 있는 표지판의 수 N (1 <= N <= 100,000)과 개방을 고려하고 있는 등산로의 수 Q (1 <= Q <= 10,000)가 주어집니다. 그 다음 줄에 N 개의 정수로 각 표지판의 해발 고도 hi 가 순서대로 주어집니다. (0 <= hi <= 20,000) 각 표지판은 입력에 주어지는 순서대로 0 번부터 N-1 번까지 번호가 매겨져 있습니다. 그 다음 Q 줄에 각 2개의 정수로 개방을 고려하고 있는 등산로의 첫 번째 표지판과 마지막 표지판의 번호 a , b (0 <= a <= b < N) 가 주어집니다.

입력 데이터의 양이 많으니 가능한 빠른 입출력 방법을 사용하시기 바랍니다.

출력

한 줄에 하나씩 개방을 고려하고 있는 각 등산로의 난이도를 출력합니다.

풀이

구간트리를 활용한 문제로, 각 구간에서 최솟값을 구하는 구간트리와 최댓값을 구하는 구간트리를 구현한 뒤, 주어진 구간에서 각 트리를 활용해 최댓값과 최솟값의 차이를 계산한다. 최솟값을 구하는 구간트리의 구조는 다음과 같다.

class SegmentTree {

	int n;
    int[] segmentArr; 

    SegmentTree(int[] arr, int n) {
    	this.n = n;
        segmentArr = new int[n * 4];

        init(arr, 0, n - 1, 1);
    }

    // node를 root로 하는 서브트리를 초기화하고, 이 구간의 최소치를 반환한다
    int init(int[] arr, int left, int right, int node) {

        if (left == right) {

            return segmentArr[node] = arr[left];
        }

        int mid = (left + right) / 2;
        
        int leftMin = init(arr, left, mid, node * 2);
        int rightMin = init(arr, mid + 1, right, node * 2 + 1);

        return segmentArr[node] = Math.min(leftMin, rightMin);
    }
    
    int query(int left, int right, int node, int nodeLeft, int nodeRight) {
    	if(right<nodeLeft || nodeRight < left)
    		return Integer.MAX_VALUE;
    	if(left<=nodeLeft && nodeRight<=right)
    		return segmentArr[node];
    	int mid = (nodeLeft + nodeRight)/2;
    	return Math.min(query(left, right, node*2, nodeLeft, mid), query(left, right, node*2+1, mid+1, nodeRight));
    }
    
    int query(int left, int right) {
    	return query(left, right, 1, 0, n-1);
    }
}

전체 요소는 1차원 배열에 저장되며, 노드 번호를 통해 접근한다. 트리의 초기화함수 init를 통해 루트 노드와 아래의 왼쪽 노드, 오른쪽 노드가 초기화하는 함수를 재귀적으로 호출하여 구현되었는데, 이 떄 왼쪽 노드값과 오른쪽 노드값의 최솟값을 해당 노드의 최솟값으로 계산하는 방식으로 구현된다. 그리고 특정 구간의 최솟값을 계산하는 함수 query에서 각 구간을 절반씩 쪼개어 재귀호출하는 방식으로 해당 구간의 최솟값을 계산하는 것을 볼 수 있다.

최댓값을 계산하는 트리는 위 클래스에서 노드의 최솟값을 최댓값으로 변경하여 구현할 수 있다. 따라서, 이 트리들을 통해 문제에서 주어진 특정 구간의 최댓값과 최솟값을 쉽게 계산할 수 있다.