[ BOJ ] 12899 : 데이터 구조 ( PLATINUM 4 ) / C

문제

자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다.

유형 1 : S에 자연수 X를 추가한다.

유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다.

입력

첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000)

둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다.

T가 1이라면 S에 추가할 X가 주어지는 것입니다. (1 ≤ X ≤ 2,000,000)

T가 2라면 X는 S에서 삭제해야 할 몇 번째로 작은 수인지를 나타냅니다. S에 최소 X개의 원소가 있음이 보장됩니다.

출력

유형 2의 쿼리 개수만큼의 줄에 각 쿼리에 대한 답을 출력합니다.

풀이 과정

구간 합 세그먼트 트리를 만들어 들어오는 수 자리에 1씩 더한 다음, 몇 번째로 작은 수인지 이분 탐색을 이용하여 출력하고 다시 1씩 감소시킨다.

#include <stdio.h>
#define SIZE 2000001

int tree[SIZE * 4] = {0,};

void update(int start, int end, int idx, int what, int value) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] += value;
		return;
	}

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what, value);
	update(mid + 1, end, idx * 2 + 1, what, value);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

int getVal(int start, int end, int idx, int key) {
	int mid = (start + end) / 2;
	if (start == end) return start;
	if (tree[idx * 2] >= key) return getVal(start, mid, idx * 2, key);
	else return getVal(mid + 1, end, idx * 2 + 1, key - tree[idx * 2]);
}

int main(void) {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		int t, x;
		scanf("%d %d", &t, &x);
		if (t == 1) {
			update(0, SIZE - 1, 1, x - 1, 1);
		}
		else {
			int res = getVal(0, SIZE - 1, 1, x) + 1;
			printf("%d\n", res);
			update(0, SIZE - 1, 1, res - 1, -1);
		}
	}
	return 0;
}