[백준] 자바 문제 풀이 2357 : 골드1

BOJ 2357 : 최솟값과 최댓값

import java.io.*;
import java.util.*;

public class Main {
	static class SegmentTree{
		private long[] max_tree;
		private long[] min_tree;
		
		SegmentTree(int n){
			double treeHeight = Math.ceil(Math.log(n)/Math.log(2))+1;
			long treeNodeCount = Math.round(Math.pow(2, treeHeight));
			max_tree = new long[Math.toIntExact(treeNodeCount)];
			min_tree = new long[Math.toIntExact(treeNodeCount)];
		}
		
		long max_init(long[] arr, int node, int start, int end) {
			if(start == end) {
				return max_tree[node] = arr[start];
			}
			return max_tree[node] = Math.max(max_init(arr, node*2, start, (start+end)/2), 
					max_init(arr, node*2+1, (start+end)/2+1, end));
		}
		
		long min_init(long[] arr, int node, int start, int end) {
			if(start == end) {
				return min_tree[node] = arr[start];
			}
			return min_tree[node] = Math.min(min_init(arr, node*2, start, (start+end)/2), 
					min_init(arr, node*2+1, (start+end)/2+1, end));
		}
		
		long min(int node, int start, int end, int left, int right) {
			if(end < left || right < start) {
				return Long.MAX_VALUE;
			} else if (left <= start && end <= right) {
				return min_tree[node];
			}
			return Math.min(min(node*2, start, (start+end)/2, left, right), 
					min(node*2+1, (start+end)/2+1, end, left, right));
		}
		
		long max(int node, int start, int end, int left, int right) {
			if(end < left || right < start) {
				return Long.MIN_VALUE;
			} else if (left <= start && end <= right) {
				return max_tree[node];
			}
			return Math.max(max(node*2, start, (start+end)/2, left, right), 
					max(node*2+1, (start+end)/2+1, end, left, right));
		}
	}

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(str.nextToken());
		int m = Integer.parseInt(str.nextToken());
		
		long[] nlist = new long[n+1];
		for(int i = 1; i <= n; i++)
			nlist[i] = Integer.parseInt(br.readLine());
		
		SegmentTree tree = new SegmentTree(n);
		tree.max_init(nlist, 1, 1, n);
		tree.min_init(nlist, 1, 1, n);
		
		for(int i = 0; i < m; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(str.nextToken());
			int y = Integer.parseInt(str.nextToken());
	
			bw.write(tree.min(1, 1, n, x, y) + " " + tree.max(1, 1, n, x, y) + "\n");
		}
		bw.flush();
		br.close();
		bw.close();
	}

}