BOJ 12899 : 데이터 구조

알고리즘 문제 전체 링크

 

https://www.acmicpc.net/problem/12899

 

참고

- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- BOJ 1655 : 가운데를 말해요 with 우선순위 큐

- BOJ 1168 : 요세푸스 문제 2

 

 

BOJ 1168 : 요세푸스 문제 2와 마찬가지로 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다.

찾은 값은 update를 이용해 다시 삭제하면 된다.

#include <stdio.h>

int N;
int tree[4194304]; 
int start, leafSize;

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

int getNumber(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx * 2]) treeIdx *= 2;
		else
		{
			index -= tree[treeIdx * 2];
			treeIdx = treeIdx * 2 + 1;
		}
	}

	return treeIdx - start;
}

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

	leafSize = 2097152;
	start = leafSize - 1;
	
	for (int i = 0; i < N; i++)
	{
		int t, x;

		scanf("%d %d", &t, &x);

		if (t == 1) update(x, 1);
		else
		{
			int number = getNumber(x);
			
			printf("%d\n", number);

			update(number, -1);
		}
	}
	
	return 0;
}