boj 2243 사탕상자

www.acmicpc.net/problem/2243

2243번: 사탕상자

사탕의 맛이 1 ~ 1000000 까지 있습니다.

저는 맛을 인덱스로 하여 세그먼트 트리를 사용하여 구간 합을 구현하였습니다.

 

A가 1일 때, B는 꺼낼 사탕의 순위입니다.

A가 2일 때, B는 넣는 사탕의 맛이고, C는 갯수이며 양수면 넣는 경우, 음수면 빼는 경우입니다.

 

A = 2가 들어오면 B 인덱스에 C만큼 추가하면 되겠고

A = 1이 들어오면 사탕의 순위를 이분탐색으로 찾습니다.

 

이분탐색은 세그먼트 트리의 값을 이용하여 범위를 찾습니다.

x가 왼쪽 자식노드의 수보다 작거나 같으면 (tree[node * 2] >= x) l ~ m 범위로 내려가고 (더 낮은 구역을 탐색)

x가 왼쪽 자식노드의 수보다 크면 (tree[node * 2 < x) m + 1 ~ r의 범위로 내려갑니다. (더 높은 구역을 탐색)

이 때 m + 1 ~ r의 범위로 이동할 때 오른쪽 자식노드의 순위를 판단해야 하기때문에 x - tree[node * 2] 한 값을 보내줍니다.

 

마지막으로 l == r 구역에 도달하면 사탕을 한개 빼줘야하므로 update를 해주고 찾은 인덱스를 리턴해줍니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static final int MAX = 1000000;
    static int tree[] = new int[(MAX + 1) * 4];
    static int N;
 
    static void update(int node, int s, int e, int idx, int diff) {
        if (idx < s || idx > e)
            return;
 
        if (s == e) {
            tree[node] += diff;
            return;
        }
 
        tree[node] += diff;
        int m = (s + e) / 2;
        update(node * 2, s, m, idx, diff);
        update(node * 2 + 1, m + 1, e, idx, diff);
    }
 
    static int binarysearch(int node, int l, int r, int x) {
        if (l == r) {
            update(1, 1, MAX, l, -1);
            return l;
        }
 
        int m = (l + r) / 2;
        if (tree[node * 2] >= x)
            return binarysearch(node * 2, l, m, x);
        else
            return binarysearch(node * 2 + 1, m + 1, r, x - tree[node * 2]);
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();
 
        N = Integer.parseInt(st.nextToken());
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
 
            if (type == 1) {
                int a = Integer.parseInt(st.nextToken());
                sb.append(binarysearch(1, 1, MAX, a)).append("\n");
            } else {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
 
                update(1, 1, MAX, a, b);
            }
        }
 
        System.out.println(sb.toString());
    }
}