백준 14428 - 수열과 쿼리 16 [Java]

문제

길이가 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번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력	예제 출력
5 5 4 3 2 1 6 2 1 3 2 1 4 1 5 3 2 3 5 1 4 3 2 3 5	3 4 4 3

---

코드

import java.util.*;

public class Main {
    private static int[] arr;
    private static int[] tree;

    private static int getMinIndex(int node) {
        if (arr[tree[node*2]] <= arr[tree[node*2+1]]) return tree[node*2];
        else return tree[node*2+1];
    }

    private static void init(int node, int start, int end) {
        if (start == end) {
            tree[node] = start;
            return;
        }
        int mid = (start + end) / 2;
        init(node*2, start, mid);
        init(node*2+1, mid+1, end);
        tree[node] = getMinIndex(node);
    }

    private static int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return -1;
        }
        if (left <= start && end <= right) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int index1 = query(node*2, start, mid, left, right);
        int index2 = query(node*2+1, mid+1, end, left, right);
        if (index1 == -1) return index2;
        else if (index2 == -1) return index1;
        else if (arr[index1] <= arr[index2]) return index1;
        else return index2;
    }

    private static void update(int node, int start, int end, int index, int value) {
        if (index < start || index > end) {
            return;
        }
        if (start == end) {
            arr[index] = value;
            tree[node] = index;
            return;
        }
        int mid = (start + end) / 2;
        update(node*2, start, mid, index, value);
        update(node*2+1, mid+1, end, index, value);
        tree[node] = getMinIndex(node);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }
        tree = new int[N*4];
        init(1, 0, N-1);
        int M = scanner.nextInt();
        for (int i = 0; i < M; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            if (a == 1) {
                update(1, 0, N-1, b-1, c);
            } else {
                int min = query(1, 0, N-1, b-1, c-1);
                System.out.println(min+1);
            }
        }
        scanner.close();
    }
}

 

값의 최솟값이 아니라 최솟값을 가지는 인덱스를 출력해야 함에 유의하자.