[백준] 14428번 수열과 쿼리16

문제 설명

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

문제 풀이

• 기본적인 세그먼트 트리 문제이다.
• 세그먼트 트리 엘리먼트로는 (index, value)를 포함한 객체를 넣어준 후 문제 조건에 맞게 작은값으로 비교하는 연산을 거쳐 세그먼트 트리 로직을 수행한다.
• 객체를 저장하므로 반드시 비교해서 트리에 저장할때 새로운 객체를 생성하여 복사하는 과정을 거쳐야 한다.

소스 코드 (JAVA)

import javax.swing.text.Segment;
import java.io.*;
import java.util.*;

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;

    public static class Point {
        int ind, v;

        public Point(int ind, int v) {
            this.ind = ind;
            this.v = v;
        }

        public Point copy() {
            return new Point(this.ind, this.v);
        }

        public static Point min(Point p1, Point p2) {
            if (p1.v < p2.v) return p1.copy();
            else if (p1.v > p2.v) return p2.copy();
            else {
                if (p1.ind < p2.ind) return p1.copy();
                else return p2.copy();
            }
        }
    }

    public static class SegmentTree {
        private final Point[] tree;

        public SegmentTree(int n) {
            double height = Math.ceil(Math.log(n) / Math.log(2)) + 1;
            long count = Math.round(Math.pow(2, height));
            tree = new Point[Math.toIntExact(count)];
        }

        public Point init(int node, int s, int e) {
            int mid = (s + e) / 2;
            if (s == e) return tree[node] = new Point(s, arr[s]);
            else return tree[node] = Point.min(init(node*2, s, mid),
                    init(node*2 + 1, mid+1, e));
        }

        public Point min(int node, int s, int e, int l, int r) {
            int mid = (s + e) / 2;
            if (e < l || r < s) return new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);
            else if (l <= s && e <= r) return tree[node];
            else return Point.min(min(node*2, s, mid, l, r),
                        min(node*2 + 1, mid+1, e, l, r));
        }

        public Point update(int node, int s, int e, int ind, int value) {
            int mid = (s + e) / 2;
            if (ind < s || e < ind) return tree[node];
            else if (s == ind && e == ind) {
                tree[node].v = value;
                return tree[node];
            } else
                return tree[node] = Point.min(update(node*2, s, mid, ind, value),
                        update(node*2 + 1, mid+1, e, ind, value));
        }
    }

    public static int N, M;
    public static int[] arr;

    public static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        SegmentTree segTree = new SegmentTree(N);
        segTree.init(1, 0, N-1);
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (c == 1) segTree.update(1, 0, N-1, a-1, b);
            else bw.write(segTree.min(1, 0, N-1, a-1, b-1).ind+1 + "\n");
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        bw.flush();
    }
}