BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐

삼성 B형 전체 링크

 

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

 

참고 

- BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리

 

 

우선순위 큐의 갱신을 이용하여 문제를 풀 수 있다.

 

update를 위해 우선순위 큐를 최악의 값으로 초기화한다.

for (int i = 0; i < 200100 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000;

 

처음의 값들은 순서대로 A₁ ~ A_N 이므로 heapIdx(id)를 각각 i = 1 ~ N으로 본다.

for (int i = 1; i <= N;i++)
{
	int a;
	scanf("%d", &a);
	push(heap, hn, a, i, heapIdx);
}

 

command 1은 A_i를 v로 바꾸라고 하였으므로 update를 이용해 변경하면 된다.

if (cmd == 1)
{
	int Ai, v;

	scanf("%d %d", &Ai, &v);
	update(heap, hn, Ai, heapIdx, v);
}

 

command 2의 경우는 가장 작은 값의 인덱스를 출력하라고 하였다.

우선순위가 가장 높은 값은 heap[1]로 구할 수 있다.

else /* cmd == 2 */
	printf("%d\n", heap[1].id);

 

인덱스가 여러 개인 경우 작은 것을 출력하라고 하였으므로, 우선순위는 아래와 같이 정의하였다.

int isMin(HEAP a, HEAP b)
{
	if (a.value < b.value) return 1;
	else if (a.value == b.value && a.id < b.id) return 1;

	return 0;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

int N, M;

typedef struct st
{
	int value;
	int id;
}HEAP;

HEAP heap[200100];
int heapIdx[200100];
int hn;

int isMin(HEAP a, HEAP b)
{
	if (a.value < b.value) return 1;
	else if (a.value == b.value && a.id < b.id) return 1;

	return 0;
}

HEAP pop(HEAP* heap, int& hn, int* heapIdx)
{
	register HEAP tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn].value = 0x7fff0000;
	heap[hn--].id = 0x7fff0000;

	for (register int i = 1; i * 2 <= hn;)
	{
		if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
		else if (isMin(heap[i * 2], heap[i * 2 + 1]))
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			heapIdx[heap[i].id] = i;
			heapIdx[heap[i * 2].id] = i * 2;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			heapIdx[heap[i].id] = i;
			heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(HEAP* heap, int& hn, int value, int id, int* heapIdx)
{
	register HEAP tmp;

	heap[++hn].value = value;
	heap[hn].id = id;
	heapIdx[id] = hn;
	for (register int i = hn; i > 1; i /= 2)
	{
		if (isMin(heap[i / 2], heap[i])) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;

		heapIdx[heap[i].id] = i;
		heapIdx[heap[i / 2].id] = i / 2;
	}
}

void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
	HEAP tmp;

	int updatehn = heapIdx[id];

	heap[updatehn].value = value;

	for (int i = updatehn; i > 1; i /= 2)
	{
		if (isMin(heap[i / 2], heap[i])) break;

		tmp = heap[i];
		heap[i] = heap[i / 2];
		heap[i / 2] = tmp;

		heapIdx[heap[i].id] = i;
		heapIdx[heap[i / 2].id] = i / 2;
	}

	for (int i = updatehn; i * 2 <= hn;)
	{
		if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
		else if (isMin(heap[i * 2], heap[i * 2 + 1]))
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			heapIdx[heap[i].id] = i;
			heapIdx[heap[i * 2].id] = i * 2;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			heapIdx[heap[i].id] = i;
			heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;

			i = i * 2 + 1;
		}
	}
}

int main(void)
{
	for (int i = 0; i < 200100 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000;

	scanf("%d", &N);

	for (int i = 1; i <= N;i++)
	{
		int a;
		scanf("%d", &a);
		push(heap, hn, a, i, heapIdx);
	}

	scanf("%d", &M);
	for (int i = 0; i < M;i++)
	{
		int cmd;
		scanf("%d", &cmd);

		if (cmd == 1)
		{
			int Ai, v;

			scanf("%d %d", &Ai, &v);
			update(heap, hn, Ai, heapIdx, v);
		}
		else /* cmd == 2 */
			printf("%d\n", heap[1].id);

	}

	return 0;
}