BOJ. Maximum and Minimum Values (2357)

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

public class Main {
	static BufferedReader br;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] line = getLine();

		int n = toi(line[0]), m = toi(line[1]);
		int[] orig = new int[n];
		int[][] seg = new int[1 << (int)(Math.ceil(Math.log(n)/Math.log(2)) + 1)][2];

		for(int iter = 0; iter < n; iter++) {
			int num = toi(br.readLine());
			orig[iter] = num;
		}

		init(seg, orig, 0, n - 1, 1);

		for(int iter = 0; iter < m; iter++) {
			line = getLine();
			int a = toi(line[0]) - 1, b = toi(line[1]) - 1;
			int[] result = get(seg, orig, 0, n - 1, a, b, 1);
			sb.append(result[0]).append(" ").append(result[1]).append("\n");
		}
		print(sb);
	}

	static int[] init(int[][] seg, int[] arr, int l, int r, int idx) {
		if(l == r) return seg[idx] = new int[] { arr[l], arr[l] };
		int mid = (l + r) / 2;
		int[] lh = init(seg, arr, l, mid, 2 * idx), rh = init(seg, arr, mid + 1, r, 2 * idx + 1);
		return seg[idx] = new int[] {
			Math.min(lh[0], rh[0]),
			Math.max(lh[1], rh[1])
		};
	}

	static int[] get(int[][] seg, int[] arr, int l, int r, int start, int end, int idx) {
		if(r < start || end < l) return new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
		if(start <= l && r <= end) return seg[idx];
		int mid = (l + r) / 2;
		int[] lh = get(seg, arr, l, mid, start, end, 2 * idx), rh = get(seg, arr, mid + 1, r, start, end, 2 * idx + 1);
		return new int[] {
			Math.min(lh[0], rh[0]),
			Math.max(lh[1], rh[1])
		};
	}


	static int sum(int[] arr, int s, int e) { int sum = 0; for(int i = s; i <= e; i++) sum+=arr[i]; return sum; }
	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}