BOJ - 2357 ) 최솟값과 최댓값

 

---

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

2357번: 최솟값과 최댓값

---

구간쿼리대 점갱신에 대표적인 예로, 구간에서 최댓값 최솟값 누적합.. 등등을 물어보는 쿼리에 대해 LogN에 

 

처리하기위해 전처리를 해준다. 사실 딱히 설명할게없다..

 

세그먼트트리 응용과 구간쿼리 구간갱신을 위한 Lazy Propagation을 공부해야겠다.

---

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

public class 최솟값과최댓값 {
	public static int maxseg[],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 );
		maxseg = new int[segsize];
		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);
		MaxSegInit(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 max = MaxQuery(1 , 0 , n-1 , left , right);
			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 MaxQuery(int node, int start, int end, int left, int right) {
		if(end < left || start >  right) return -1;
		if(left <= start && end <= right) return maxseg[node];
		int mid = (start+end)>>1;
		return Math.max(MaxQuery(2*node, start, mid, left, right), MaxQuery(2*node+1, mid+1, end, left, right));
	}
	private static int MaxSegInit(int node, int start, int end) {
		if(start== end) {return maxseg[node] = number[start];}
		int mid = (start+end)>>1;
		return maxseg[node] = Math.max(MaxSegInit(2*node, start, mid), MaxSegInit(2*node+1, mid+1, end));
	}
	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));
	}

}

---

크게 설명할게 없다..