BOJ - 10868 ) 최솟값

---

https://www.acmicpc.net/problem/10868

10868번: 최솟값

---

https://algorithmstudy-mju.tistory.com/128

BOJ - 2357 ) 최솟값과 최댓값

이분제의 부분문제인거같다. 세그먼트트리에 최솟값을 적어두고, 쿼리가 일어날때에 관련이없으면 매우큰수를

 

리턴하여서 비교하지 못하게한다.. 사실 Update가 안일어나서 굳이 이렇게 안풀어도 될거같다..

 

---

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

public class 최솟값 {
	public static int minseg[];
	public static int number[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int segsize = (int) Math.pow(2, Math.ceil(Math.log10(n)/Math.log10(2))+1 );
		minseg = new int[segsize];
		number = new int[n];
		for(int i = 0 ; i < n ; i++) {
			st= new StringTokenizer(br.readLine());
			number[i] =  Integer.parseInt(st.nextToken());
		}
		MinSegInit(1,0,n-1);
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken())-1;
			int right = Integer.parseInt(st.nextToken())-1;
			int min = MinQuery(1 , 0 , n-1 , left , right);
			sb.append(min +"\n");
		}
		System.out.println(sb);
	}
	private static int MinQuery(int node, int start, int end, int left, int right) {
		if(end < left || start >  right) return 2147000000;
		if(left <= start && end <= right) return minseg[node];
		int mid = (start+end)>>1;
		return Math.min(MinQuery(2*node, start, mid, left, right), MinQuery(2*node+1, mid+1, end, left, right));
	}
	private static int MinSegInit(int node, int start, int end) {
		if(start== end) {return minseg[node] = number[start];}
		int mid = (start+end)>>1;
		return minseg[node] = Math.min(MinSegInit(2*node, start, mid), MinSegInit(2*node+1, mid+1, end));
	}

}

---