사탕의 맛의 범위가 으로 정해져 있다. 누적 합을 이용한 세그먼트 트리인 펜윅 트리를 이용하면 삽입과 삭제는 에 가능한데, k번째 값은 어떻게 구할 수 있을까?
펜윅 트리의 함수는 x이하의 맛을 가지는 사탕의 개수를 반환해주는데, 이 함수의 값은 단조 증가하므로 이분 탐색을 적용할 수 있다. 번째 맛은 가 k와 같거나 크게 되는 그 순간의 x가 된다.
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;
}
}
을 사탕의 총 개수라고 할 때, 사탕을 몇개를 삽입하건 간에 어차피 정수 하나를 삽입하는 것이므로 모든 삽입과 삭제는 이고 총 번의 쿼리가 주어지므로