BOJ 2243 사탕 상자

빈 사탕 상자에서 시작해서 주어진 입력에 따라 우선순위가 a인 사탕을 b개 넣거나 뺀다(먹지는 않음). 그러면서 도중에 우선순위가 x번째로 높은 사탕을 빼서 먹을 것인데, 빼서 먹게 되는 사탕의 우선순위를 출력하는 것이 문제이다.

일단 priority queue(-1을 곱해서 넣고 뺄 때 -1을 붙여서 min heap으로 활용)를 활용해서 하면 될 것 같아보이는데, 좀 걸리는 게 사탕의 총 개수가 최대 20억개라는 것이다. 예를 들어 10억번째로 우선순위가 높은 사탕이 뭔지 찾으라고 하면 priority queue에서 10억 번을 빼야하나? 음 아니다! 입력으로 주어지는 사탕을 넣고 빼고 하는 횟수의 수가 최대 10만 번이다. 그렇다는 것은 일단 prirority queue에는 (사탕의 우선순위, 그 사탕의 개수)가 최대 10만 개 들어가있다는 것이다. 음 그래도 query까지 하면 시간이 꽤 걸릴 것 같은데...

아... 굳이 priority queue를 쓸 필요가 없다. 우선순위는 최대 백만까지다. 그냥 배열의 인덱스로 우선순위를 표시하고 배열에는 그 우선순위에 해당하는 사탕의 개수를 기록해도 될 것이다. 그럼 찾는 것은 어떻게 빨리 찾을 수 있을까? 누적합을 이용해서 이분탐색을 하면 빠르게 찾을 수 있을 것이다. 그런데 누적합의 업데이트가 빈번하다... 그렇다면 fenwick tree를 쓰면 어떨까? 한 번 구현해 봐야겠다. 예제 케이스도 제대로 안 나오길래 봤더니 이분 탐색이 문제였다. 이분 탐색을 구현할 때 좀 헷갈리고 까다로웠는데, 주의해야 한다.
AC를 받았다!
Fenwick Tree를 이용해서 누적합을 logN만에 업데이트 할 수 있고, 이분 탐색을 이용해서 x번째로 우선순위가 높은 사탕을 logN(이분탐색)*logN(누적합 구하기)만에 찾을 수 있다.(N은 100만)