[Java] 백준 3653 영화 수집 - Lazy Segment Tree

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

3653번: 영화 수집

leaf 노드의 경우 좌측부터 i번 영화가 node[i] 번째에 놓여있도록 하였다.

하지만 탐색 회수를 최적화하기 위해

해당 노드를 root로 가지는 트리에 대하여 mintree, maxtree로 나누어서

mintree[node] >= v 라면 그 트리는 놓여있는 위치의 값을 더해선 안되므로 return

maxtree[node] < v 라면 그 트리의 모든 노드는 1을 더해주므로 minlazy, maxlazy 모두 ++

 

솔직히 한번에 맞을줄 상상도 못했다.

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

public class p4_3653 {
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int n, m;
    static int[] mintree, maxtree, minlazy, maxlazy;

    public static void main(String[] args) {
        int t = fs.nextInt();
        while (t-- > 0){
            n = fs.nextInt();
            m = fs.nextInt();

            mintree = new int[n * 4];
            maxtree = new int[n * 4];
            minlazy = new int[n * 4];
            maxlazy = new int[n * 4];

            init(1, n, 1);

            while (m-- > 0){
                int num = fs.nextInt();
                int index = find(1, n, 1, num);
                pw.print((index - 1) + " ");
                update(1, n, 1, index);
                change(1, n, 1, num);
            }
            pw.println();
        }

        
        pw.close();
    }

    static void change(int lo, int hi, int node, int i){
        lazy(lo, hi, node);

        if (i < lo || hi < i) return;
        if (lo == hi){
            mintree[node] = 1;
            maxtree[node] = 1;
            return;
        }
        int mid = (lo + hi) / 2;
        change(lo, mid, node * 2, i);
        change(mid + 1, hi, node * 2 + 1, i);

        mintree[node] = Math.min(mintree[node * 2], mintree[node * 2 + 1]);
        maxtree[node] = Math.max(maxtree[node * 2], maxtree[node * 2 + 1]);
    }

    static void update(int lo, int hi, int node, int v){
        lazy(lo, hi, node);

        if (maxtree[node] < v){
            minlazy[node]++;
            maxlazy[node]++;
            return;
        }
        if (mintree[node] >= v) return;

        int mid = (lo + hi) / 2;
        update(lo, mid, node * 2, v);
        update(mid + 1, hi, node * 2 + 1, v);
    }

    static int find(int lo, int hi, int node, int i){
        lazy(lo, hi, node);

        if (i < lo || hi < i) return -1;
        if (lo == hi) return mintree[node];

        int mid = (lo + hi) / 2;
        return Math.max(find(lo, mid, node * 2, i), find(mid + 1, hi, node * 2 + 1, i));
    }

    static void lazy(int lo, int hi, int node){
        if (minlazy[node] != 0){
            mintree[node] += minlazy[node];
            if (lo != hi){
                minlazy[node * 2] += minlazy[node];
                minlazy[node * 2 + 1] += minlazy[node];
            }
            minlazy[node] = 0;
        }

        if (maxlazy[node] != 0){
            maxtree[node] += maxlazy[node];
            if (lo != hi){
                maxlazy[node * 2] += maxlazy[node];
                maxlazy[node * 2 + 1] += maxlazy[node];
            }
            maxlazy[node] = 0;
        }
    }

    static void init(int lo, int hi, int node){
        if (lo == hi){
            mintree[node] = lo;
            maxtree[node] = lo;
            return;
        }

        int mid = (lo + hi) / 2;
        init(lo, mid, node * 2);
        init(mid + 1, hi, node * 2 + 1);

        mintree[node] = Math.min(mintree[node * 2], mintree[node * 2 + 1]);
        maxtree[node] = Math.max(maxtree[node * 2], maxtree[node * 2 + 1]);
    }





    // ----------input function----------

    static void sort(int[] a) {
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a)
            L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++)
            a[i] = L.get(i);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}