[BOJ] 백준 14428번 수열과 쿼리 16 (Java)

#14428 수열과 쿼리 16

난이도 : 골드 1

유형 : 세그먼트 트리 / 인덱스 트리

14428번: 수열과 쿼리 16

▸ 문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다. (1 ≤ i ≤ j ≤ N, 1 ≤ v ≤ 109)

수열의 인덱스는 1부터 시작한다.

▸ 입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리가 주어진다.

▸ 출력

2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

 

문제 풀이  

2번 쿼리에서 원하는 것은 인덱스이기 때문에 최소 인덱스 트리로 설계해줘야 한다. 수열을 비교해서 최솟값을 지니는 인덱스를 세그먼트 트리에 넣어주면 된다.

 

세그먼트 트리에 대한 자세한 설명은 여기를 참고해주세요

 

예제를 바탕으로 처음 인덱스 트리 초기화하면 다음과 같이 생성된다.

 

최소 인덱스 트리

 

값 변경하기

값 변경도 수열을 비교한 다음 그에 해당하는 인덱스를 넣어주면 된다. 예를 들어 5번 노드를 3으로 바꾼다고 하면 다음과 같이 업데이트된다.

 

값 변경하기

 

최솟값 인덱스 출력하기

3번 ~ 5번에서 최솟값을 가지는 인덱스를 구하면 다음과 같이 비교를 통해 2값을 가지는 4번 인덱스가 출력된다.

 

최솟값 인덱스 출력하기

 

풀이 코드 

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

public class Main {

	static int[] arr, tree;
	static int n;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n+1];
		tree = new int[4*n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr[0] = Integer.MAX_VALUE;
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		init(1, n, 1);
		StringBuilder sb = new StringBuilder();
		int m = Integer.parseInt(br.readLine());
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(op == 1) {
				arr[a] = b;
				update(1, n, 1, a);
			}else {
				sb.append(getMin(1, n, 1, a, b)+"\n");
			}
		}
		
		System.out.println(sb.toString());
		
	}
    
	static int init(int s, int e, int node) {
		if(s == e) return tree[node] = s;
		
		int mid = (s+e)/2;
		int left = init(s, mid, node*2);
		int right =  init(mid+1, e, node*2+1);
		return tree[node] =  getIndex(left,right); 
	}
	
	static int update(int s, int e, int node, int idx) {
		if(s > idx || e < idx ) return tree[node];
		if(s == e)  return tree[node] = idx;
		
		int mid = (s+e)/2;
		int left = update(s, mid, node*2, idx);
		int right =  update(mid+1, e, node*2+1, idx);
		return tree[node] = getIndex(left,right);
	}
	
	static int getMin(int s, int e, int node, int l, int r) {
		if(r < s || l > e ) return 0;
		if(l <= s && e <= r) {
			return tree[node];
		}
		
		int mid = (s+e)/2;
		int left = getMin(s, mid, node*2, l, r);
		int right =  getMin(mid+1, e, node*2+1, l, r);
		return getIndex(left, right);
	}
	
	static int getIndex(int left, int right) {
		if(arr[left] == arr[right]) return getMin(left, right);
		else if(arr[left] < arr[right]) return left;
		else return right;
	}
	
	static int getMin(int left, int right) {
		if(left < right) {
			return left;
		}else return right;
	}	
}