StepByStep

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.

풀이.

이 문제는 Segment-Tree와 관련된 문제이다. 기본 세그먼트 트리를 기반으로 했을 때 주요 문제의 포인트는 단말 노드가 아닌 노드들은 모두 가장 작은 값을 올려 두는 것이다. 이를 제외한다면 기본 세그먼트 트리의 기본문제와 동일하다.

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

public class Main {

    static long[] arr,tree;
        
    public static void main(String[] args) throws IOException {
    
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        arr = new long[N+1];
        tree = new long[4*N];

        for (int i = 0; i < N; i++) 
            arr[i] = Integer.parseInt(bf.readLine());
        
        
        initTree(0,N-1,1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            bw.write(searchTree(0,N-1,1,Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1)+"\n");
        }
        
        bw.close();
        
    }
    
    public static long initTree(int start, int end, int index){//세그먼트 트리를 만드는 함수
        
        if(start == end)
            return  tree[index] = arr[start];
            
        else{
            int mid = (start+end)/2;
            return tree[index] = Long.min(initTree(start,mid,index*2), initTree(mid+1,end,index*2+1));
        }
    }
    
    public static long searchTree(int start, int end, int index, int left, int right){
    //세그먼트 트리 탐색 함수
      
      	if(start > right || end < left)
            return Integer.MAX_VALUE;
        
        if(start>=left && end <= right)
            return tree[index];
        
        int mid = (start + end)/2;

        return Long.min(searchTree(start,mid,index*2,left,right), searchTree(mid+1,end,index*2+1,left,right));

    }
}