백준 사탕상자(2243)

사탕상자

1. 힌트

1) 가지고 있는 사탕들의 맛과 그 개수를 유지해야 하고, 사탕의 개수가 최대 $2 \times 10^8$이므로 삽입과 삭제가 $O(lgN)$에 이루어져야 한다.

2) 구간 합을 저장하는 세그먼트 트리를 이용하면 위 조건은 충족 시킬 수 있다.

3) k번째 값의 삭제가 필요한데, 누적합을 이용하면 이분 탐색이 가능해서 $O(lgN)$에 가능하다.

2. 접근

7) 문제를 분해할 수 있을까?

사탕의 맛의 범위가 $[1, 10^6]$으로 정해져 있다. 누적 합을 이용한 세그먼트 트리인 펜윅 트리를 이용하면 삽입과 삭제는 $O(lgN)$에 가능한데, k번째 값은 어떻게 구할 수 있을까?
펜윅 트리의 $sum(x)$함수는 x이하의 맛을 가지는 사탕의 개수를 반환해주는데, 이 함수의 값은 단조 증가하므로 이분 탐색을 적용할 수 있다. $k$번째 맛은 $sum(x)$가 k와 같거나 크게 되는 그 순간의 x가 된다.

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder ans = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		FenwickTree t = new FenwickTree();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			if (A == 1) {
				int x = t.kth(B);
				ans.append(x).append("\n");
				t.add(x, -1);
			} else {
				t.add(B, Integer.parseInt(st.nextToken()));
			}
		}
		System.out.print(ans);
	}

}

class FenwickTree {
	int[] tree = new int[1000001];
	
	void add(int pos, int val) {
		while (pos < tree.length) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
	
	int sum(int pos) {
		int ret = 0;
		while (pos > 0) {
			ret += tree[pos];
			pos -= (pos & -pos);
		}
		return ret;
	}
	
	// k번째 값을 반환
	int kth(int k) {
		// f(x) = x 맛 이하의 개수
		// f(lo) < k && f(hi) >= k인 hi를 반환
		int lo = 0; int hi = 1000000;
		while (lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			if (mid != 0 && sum(mid) >= k) hi = mid;
			else lo = mid;
		}
		return hi;
	}
	
}

1) 시간 복잡도

$M$을 사탕의 총 개수라고 할 때, 사탕을 몇개를 삽입하건 간에 어차피 정수 하나를 삽입하는 것이므로 모든 삽입과 삭제는 $O(lgM)$이고 총 $O(N)$번의 쿼리가 주어지므로 $O(NlgM)$

2) 테스트 케이스