[ BOJ ] 2243 : 사탕상자 ( PLATINUM 5 ) / C

문제

수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다.

각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다.

수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 꺼낼 사탕을 골라내는 일은 매우 어렵다. 수정이를 도와주는 프로그램을 작성하시오.

입력

첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다. 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 C는 그러한 사탕의 개수이다. C가 양수일 경우에는 사탕을 넣는 경우이고, 음수일 경우에는 빼는 경우이다. 맨 처음에는 빈 사탕상자에서 시작한다고 가정하며, 사탕의 총 개수는 2,000,000,000을 넘지 않는다. 또한 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다.

출력

A가 1인 모든 입력에 대해서, 꺼낼 사탕의 맛의 번호를 출력한다.

풀이 과정

세그먼트 트리에서 같은 값 중 가장 왼쪽 값을 이분 탐색으로 찾아야 한다. 이분 탐색을 생각보다 너무 어렵게 접근했던 문제다.

#include <stdio.h>
#define SIZE 210000
typedef long long LL;

int arr[SIZE];
LL tree[SIZE * 4];

void init(int start, int end, int idx, int m) {
	if (start == end) {
		if (start < m) {
			arr[start] = 0;
			tree[idx] = 0;
			return;
		}
		else {
			arr[start - m] = start;
			tree[idx] = 1;
			return;
		}
	}

	int mid = (start + end) / 2;
	init(start, mid, idx * 2, m);
	init(mid + 1, end, idx * 2 + 1, m);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

LL interval_sum(int start, int end, int idx, int left, int right) {
	if(end < left || right < start) return 0;
	if(left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	return interval_sum(start, mid, idx * 2, left, right) + interval_sum(mid + 1, end, idx * 2 + 1, left, right);
}

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 main(void) {
	int test;
	scanf("%d", &test);

	for(int t = 0; t < test; t++) {
		int n, m;
		scanf("%d %d", &n, &m);
		
		init(0, SIZE - 1, 1, m);

		int top = m - 1;
		for(int i = 0; i < m; i++) {
			int num;
			scanf("%d", &num);

			printf("%lld ", interval_sum(0, SIZE - 1, 1, 0, arr[num - 1] - 1));
			update(0, SIZE - 1, 1, arr[num - 1], -1);
			update(0, SIZE - 1, 1, top, 1);
			arr[num - 1] = top--;
		}
		printf("\n");
	}
	return 0;
}