MaxValueAndMinValue.java

package problem.boj;

import java.util.Scanner;

/**
 * Created by Jinseoung on 2016-12-30.
 */
public class MaxValueAndMinValue {

    // 세그먼트 트리 구현체
    static class SegmentTree {

        int[] numbers;
        MaxAndMin[] tree;


        public static int log2( int bits )
        {
            int log = 0;
            if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
            if( bits >= 256 ) { bits >>>= 8; log += 8; }
            if( bits >= 16  ) { bits >>>= 4; log += 4; }
            if( bits >= 4   ) { bits >>>= 2; log += 2; }
            return log + ( bits >>> 1 );
        }

        public SegmentTree(int[] numbers) {
            this.numbers = numbers;

            tree = new MaxAndMin[1<<(log2(numbers.length-1)+2)+1];

            this.createTree(1, 1, numbers.length-1);
        }

        // 최초 생성시 사용하는 tree 생성 코드
        private MaxAndMin createTree (int node, int start, int end) {
            if(start == end) {
                return tree[node] =  new MaxAndMin(numbers[start], numbers[start]);
            } else {
                int mid = (start+end)/2;
                int childLeft = node + node, childRight = childLeft + 1;

                return tree[node] = this.createTree(childLeft, start, mid).merge(this.createTree(childRight, mid + 1, end));
            }
        }

        public MaxAndMin getMaxMinOfRange(int from, int to) {
            return this.getMaxMinOfRange(1, 1, numbers.length-1, from, to);
        }

        private  MaxAndMin getMaxMinOfRange(int node, int start, int end, int from, int to) {
            if(from <= start && end <= to) {
                return tree[node];
            } else if (to < start || end < from){
                return MaxAndMin.WORST;
            } else {
                int mid = (start+end)/2;
                int childLeft = node + node, childRight = childLeft + 1;

                return this.getMaxMinOfRange(childLeft, start, mid, from, to).merge(this.getMaxMinOfRange(childRight, mid+1, end, from, to));
            }
        }
    }

    static class MaxAndMin {
        static final MaxAndMin WORST = new MaxAndMin(Integer.MIN_VALUE, Integer.MAX_VALUE);;

        public int max, min;

        public MaxAndMin(int max, int min) {
            this.max = max;
            this.min = min;
        }

        public MaxAndMin merge (MaxAndMin target) {
            return new MaxAndMin(Math.max(this.max, target.max), Math.min(this.min, target.min));
        }

        @Override
        public String toString() {
            return String.format("%d %d", this.min, this.max);
        }
    }

    static Scanner sc = new Scanner(ClassLoader.getSystemResourceAsStream("problem/boj/MaxValueAndMinValue.testcase"));

    public static void main(String[] args) {

        int N = sc.nextInt(),
            K = sc.nextInt();

        int[] numbers = new int[N+1];

        for(int i = 1; i <= N; i++) numbers[i] = sc.nextInt();

        SegmentTree segmentTree = new SegmentTree(numbers);

        for(int i = 0; i < K; i++) {
            System.out.println(segmentTree.getMaxMinOfRange(sc.nextInt(), sc.nextInt()).toString());
        }
    }
}