[백준 14428] 수열과 쿼리 16

package javaSana.Day0920.segmentTree;

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

public class B_14428 {

	static class Point {
		int idx;
		int value;

		Point(int i, int v) {
			this.idx = i;
			this.value = v;
		}
	}

	static int N, M;
	static int[] arr;
	static Point[] tree;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		M = Integer.parseInt(br.readLine());
		tree = new Point[N*4];
		
		init(1, N, 1);
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int mode = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			if (mode == 1) { // arr[a] = b
				arr[a] = b;
				update(1, N, 1, a, b);
			} else if (mode == 2) { // a ~ b 에서 min값 출력
				Point p = query(1, N, 1, a, b);
				System.out.println(p.idx);
			}

		}
	}

	static Point init(int start, int end, int node) {
		if (start == end)
			return tree[node] = new Point(start, arr[start]);

		int mid = (start + end) / 2;
		
		Point lPoint = init(start, mid, node * 2);
		Point rPoint = init(mid + 1, end, node * 2 + 1);
		
		return tree[node] = compareTo(lPoint, rPoint);
	}

	static void update(int start, int end, int node, int idx, int change) {
		if (idx < start || end < idx) {
			return;
		}
		if (start == end && start == idx) {
			
				tree[node].value = change;
			
		} 
		if(start != end){
			int mid = (start + end) / 2;

			update(start, mid, node * 2, idx, change);
			update(mid + 1, end, node * 2 + 1, idx, change);
			tree[node] = compareTo(tree[node * 2], tree[node * 2 + 1]);
		}

	}

	static Point query(int start, int end, int node, int left, int right) {
		if (right < start || end < left)
			return new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);

		if (left <= start && end <= right) {
			return tree[node];
		}

		int mid = (start + end) / 2;
		Point lPoint = query(start, mid, node * 2, left, right);
		Point rPoint = query(mid + 1, end, node * 2 + 1, left, right);

		return compareTo(lPoint, rPoint);

	}

	static Point compareTo(Point p1, Point p2) {
		if (p1.value == p2.value) {
			if (p1.idx < p2.idx) {
				return new Point(p1.idx, p1.value);
			} else {
				return new Point(p2.idx, p2.value);
			}
		} else {
			if (p1.value < p2.value) {
				return new Point(p1.idx, p1.value);
			} else {
				return new Point(p2.idx, p2.value);
			}
		}
	}

}