최솟값과 최댓값

# 문제링크

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

# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64

# 풀이

public class BOJ2357 {
    static int N, M;
    static int a, b;
    static int arr[], segMinArr[], segMaxArr[];
 
    static void init(int N) {
        segMinArr = new int[N*4];
        segMaxArr = new int[N*4];
        Arrays.fill(segMinArr, Integer.MAX_VALUE);
        Arrays.fill(segMaxArr, Integer.MIN_VALUE);
    }
    
    static int createMinTree(int arr[], int left, int right, int node) {
        if (left == right) return segMinArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMinArr[node] = Math.min(createMinTree(arr, left, mid, node*2), createMinTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMinQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MAX_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMinArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.min(getMinQuery(left, right, node*2, nodeLeft, mid), getMinQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    static int createMaxTree(int arr[], int left, int right, int node) {
        if (left == right) return segMaxArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMaxArr[node] = Math.max(createMaxTree(arr, left, mid, node*2), createMaxTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMaxQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MIN_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMaxArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.max(getMaxQuery(left, right, node*2, nodeLeft, mid), getMaxQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        init(N);
        createMinTree(arr, 0, N-1, 1);
        createMaxTree(arr, 0, N-1, 1);
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;
            
            sb.append(getMinQuery(a, b, 1, 0, N-1) + " " +getMaxQuery(a, b, 1, 0, N-1) + "\n");
        }
        System.out.println(sb.toString());
    }
}