072 : 최솟값 찾기 2

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 정수 배열 A번째 ~ B번째 중 가장 작은 정수 찾기 a~b 쌍이 M개 주어진다		I // N M (2) 1번째 값 ... (N+1) N번째 값 (N+2) 1번째 ab 쌍 ... (N+M+1) M번째 ab쌍 O // ab 사이 최솟값을 차례대로 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    // box recognition
    static long[] tree;
    
    public static void main(String[] args) throws IOException {
        
        // ISC
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // p.R
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int treeHeight = 0;
        int length = N;
        while (length != 0) {
            length /= 2;
            treeHeight++;
        }
        
        // b.R
        int treeSize = (int) Math.pow(2, treeHeight+1);
        int leftNodeStartIndex = treeSize/2 - 1;
        tree = new long[treeSize+1];
        for (int i = 0; i < tree.length; i++) {
            tree[i] = Integer.MAX_VALUE;
        }
        for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        setTree(treeSize-1);
        
        // Operating pMin + OES
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            s = s + leftNodeStartIndex;
            e = e + leftNodeStartIndex;
            System.out.println(pMin(s, e));
        }
        br.close();
    }
    
    // External Module : pMin
    private static long pMin(int s, int e) {
        long Min = Long.MIN_VALUE;
        while (s <= e) {
            if (s % 2 == 1) {
                Min = Math.min(Min, tree[s]);
                s++;
            }
            s = s / 2;
            if (e % 2 == 0) {
                Min = Math.min(Min, tree[e]);
                e--;
            }
            e = e / 2;
        }
        return Min;
    }
    
    // External Module : setTree
    private static void setTree(int size) {
        while (size != 1) {
            if (tree[size / 2] > tree[size])
                tree[size / 2] = tree[size];
            size--;
        }
    }
    
    
}