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

14428번: 수열과 쿼리 16

---

arr[0] = Integer.MAX_VALUE

범위 밖 범위 index 0참조

---

---

• 제목

수열과 쿼리 16

---

• 조건

시간 제한 : 2 초

메모리 제한 : 512 MB 

---

• 문제

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

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

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

---

• 입력

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

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

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

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

---

• 출력

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

---

예제 입력1	예제 출력1
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.io.*;
import java.util.*;

public class Main{
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] segmentTree, arr;
    static int init(int left, int right, int node){
        if(left == right) return segmentTree[node] = left;
        int mid = (left + right) / 2;
        int leftindex = init(left, mid, node * 2);
        int rightindex = init(mid + 1, right, node * 2 + 1);
        if(arr[leftindex] == arr[rightindex]) return segmentTree[node] = Math.min(leftindex, rightindex);
        else return segmentTree[node] = arr[leftindex] > arr[rightindex] ? rightindex : leftindex;
    }

    static int query(int left, int right, int node, int start, int end){
        if(end < left || right < start) return 0;
        if(start <= left && right <= end) return segmentTree[node];
        int mid = (left + right) / 2;
        int leftindex = query(left, mid, node * 2, start, end);
        int rightindex = query(mid + 1, right, node * 2 + 1, start, end);
        if(arr[leftindex] == arr[rightindex]) return Math.min(leftindex, rightindex);
        else return arr[leftindex] > arr[rightindex] ? rightindex : leftindex;
    }

    static int update(int left, int right, int node, int index){
        if(left == right) return segmentTree[node];
        if(index < left || right < index) return segmentTree[node];
        int mid = (left + right) / 2;
        int leftindex = update(left, mid, node * 2, index);
        int rightindex = update(mid + 1, right, node * 2 + 1, index);
        if(arr[leftindex] == arr[rightindex]) return segmentTree[node] = Math.min(leftindex, rightindex);
        else return segmentTree[node] = arr[leftindex] > arr[rightindex] ? rightindex : leftindex;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        arr[0] = Integer.MAX_VALUE;
        segmentTree = new int[1 << ((int)Math.ceil(Math.log(N)/Math.log(2)) + 1)];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        init(1, N, 1);
        M = Integer.parseInt(br.readLine());
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken());
            if(o == 1){
                int index = Integer.parseInt(st.nextToken());
                int value = Integer.parseInt(st.nextToken());
                arr[index] = value;
                update(1, N, 1, index);
            }
            else{
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                sb.append(query(1, N, 1, start, end)).append('\n');
            }
        }
        System.out.println(sb);
    }
}