백준 Java | BOJ 2243 사탕상자

package DAY04.P2243;

import java.io.*;

public class Main {
    static int n;
    static int[] candy;
    static int[] tree;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/DAY04/P2243/input.txt"));
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        candy = new int[1000001];
        int S = 1;
        int MAX = 1000000;
        while (S < MAX){
            S *= 2;
        }
        tree = new int[S * 2];

        for (int i=0;i<n;i++){
            String[] input = bf.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            if (a==2){
                // 사탕을 넣는 경우??
                int c = Integer.parseInt(input[2]);
                update(1, S, 1, b, c);
            } else {
                // 사탕을 꺼내는 경우
                int answer = query(1, S, 1, b);
                System.out.println(answer);
                update(1, S, 1, answer, -1);
            }
        }
    }
    public static int query(int left, int right, int node, int target){
        // left -> 사탕 찾음
        if (left == right){
            return left;
        } else {
            // internal node
            int mid = (left + right) / 2;
            if (tree[node*2-1]>=target){
                return query(left, mid, node * 2, target);
            } else {
                return query(mid + 1, right, node * 2 + 1, target-tree[node*2-1]);
            }
        }
    }
    public static void update(int left, int right, int node, int target, long diff){
        // 1. 연관 없음
        if (target < left || right < target) {
            return;
        }
        // 2. 연관 있음
        else {
            tree[node-1] += diff;
            if (left != right){
                // internal node
                int mid = (left + right) / 2;
                update(left, mid, node * 2, target, diff);
                update(mid + 1, right, node * 2 + 1, target, diff);
            }
        }
    }
}