[백준/C++] 2243번: 사탕상자

방법

코드

#include<bits/stdc++.h>
#define MAX 1000001	// 1 ~ 1,000,000 맛종류
using namespace std;

int n, B;
int IDT[MAX * 4];

void update(int p, int v) {
	p += (B - 1);
	IDT[p] += v;
	while (p /= 2) {
		IDT[p] = IDT[p * 2] + IDT[p * 2 + 1];
	}
}

int search(int k) {	// k번째 찾기
	int p = 1;
	while (p < B) {	// Leaf 노드될 때까지
		p *= 2;	// 왼쪽 child로
		if (IDT[p] < k) {	// 오른쪽 트리에 k번째 있음
			k -= IDT[p];	// 구간합 빼주기
			p += 1;	// 오른쪽 트리로 이동
		}
	}
	return p - (B - 1);
}

int main() {
	scanf("%d", &n);
	for (B = 1; B < MAX; B <<= 1);
	for (int i = 0, a, b, c; i < n; i++) {
		scanf("%d", &a);
		if (a == 1) {	// 해당 우선순위의 사탕 1개 뺌
			scanf("%d", &b);	// 우선순위 사탕 찾기
			c = search(b);
			printf("%d\n", c);
			update(c, -1);	// 사탕 빼기
		}
		else {	// 해당 우선순위에 사탕 c개 넣거나 뺌
			scanf("%d %d", &b, &c);
			update(b, c);
		}
	}
	return 0;
}