[ BOJ ][JAVA][2357] 최솟값과 최댓값

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	192 MB	12676	5952	4282	50.041%

문제

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이하의 값을 갖는다.

입력

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

출력

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

예제 입력 1

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

예제 출력 1

5 100
38 100
20 81
5 81

코드

/*
    최솟값과 최댓값
    세그먼트 트리

    구간별 최소값을 저장하는 트리, 최댓값을 저장하는 트리를 각각 생성한다.
*/
import java.io.*;
import java.util.*;
public class p2357 {
    static class SegmentTree {
        long[] minTree, maxTree;
        public SegmentTree() {
            minTree = new long[n * 4];
            maxTree = new long[n * 4];
        }
        long minInit(long[] tree, int node, int start, int end) {
            if (start == end) return minTree[node] = arr[start];
            int mid = (start + end) / 2;
            return minTree[node] = Math.min(minInit(tree, node * 2, start, mid), minInit(tree, node * 2 + 1, mid + 1, end));
        }

        long maxInit(long[] tree, int node, int start, int end) {
            if (start == end) return maxTree[node] = arr[start];
            int mid = (start + end) / 2;
            return maxTree[node] = Math.max(maxInit(tree, node * 2, start, mid), maxInit(tree, node * 2 + 1, mid + 1, end));
        }

        // left ~ right 범위 내의 최솟값을 찾는다.
        long minFind(long[] tree, int node, int start, int end, int left, int right) {
            if (right < start || end < left) return Integer.MAX_VALUE;

            if (left <= start && end <= right) return minTree[node];

            int mid = (start + end) / 2;

            return Math.min(minFind(minTree, node * 2, start, mid, left, right), minFind(minTree, node * 2 + 1, mid + 1, end, left, right));
        }

        // left ~ right 범위 내의 최댓값을 찾는다.
        long maxFind(long[] tree, int node, int start, int end, int left, int right) {
            if (right < start || end < left) return 0;

            if (left <= start && end <= right) return maxTree[node];

            int mid = (start + end) / 2;

            return Math.max(maxFind(minTree, node * 2, start, mid, left, right), maxFind(minTree, node * 2 + 1, mid + 1, end, left, right));
        }
    }
    static int n, m;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        SegmentTree sgTree = new SegmentTree();
        sgTree.minInit(sgTree.minTree, 1, 1, n);
        sgTree.maxInit(sgTree.maxTree, 1, 1, n);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(sgTree.minFind(sgTree.minTree, 1, 1, n, a, b)).append(" ").append(sgTree.maxFind(sgTree.maxTree, 1, 1, n, a, b));
            sb.append("\n");
        }
        System.out.println(sb.toString());

    }
}