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

삼성 B형 전체 링크

 

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

 

참고 

- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)

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

- BOJ 10868 : 최솟값

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

 

 

BOJ 10868 : 최솟값을 관리할 때, 세그먼트 트리를 이용하였는데,

이 문제에서는 값이 변경되고, index도 같이 관리하면 된다.

 

따라서 tree는 아래의 구조체로 만들어진다.

typedef struct st
{
	int index;
	int value;
}NODE;

 

같은 값인 경우는 index가 더 작은 값을 출력하기 위해 isMin을 다음과 같이 정의한다.

NODE isMin(NODE a, NODE b)
{
	if (a.value < b.value) return a;
	if (a.value == b.value && a.index < b.index) return a;

	return b;
}

init과 getMin은 다음과 같다.

NODE init(int left, int right, int node)
{
	if (left == right) return tree[node] = A[left];
	
	int mid = (left + right) / 2;

	return tree[node]
		= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}

NODE getMin(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return MaxNode;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	return isMin(getMin(left, mid, a, b, node * 2), getMin(mid + 1, right, a, b, node * 2 + 1));
}

 

최악의 값을 return하기 위해 MaxNode는 아래와 같이 정의를 해두었다.

MaxNode.index = 0x7fff0000;
MaxNode.value = 0x7fff0000;

 

update는 left와 right가 같을 때 갱신하고, 이후 더 작은 값을 리턴하도록 수정한다.

NODE update(int left, int right, int node, int index, int value)
{
	if (index < left || right < index) return tree[node];
	if (left == right)
	{
		tree[node].value = value;

		return tree[node];
	}

	int mid = (left + right) / 2;
	NODE leftNode = update(left, mid, node * 2, index, value);
	NODE rightNode = update(mid + 1, right, node * 2 + 1, index, value);

	return tree[node] = isMin(leftNode, rightNode);
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

typedef long long int ll;

int N, M;

typedef struct st
{
	int index;
	int value;
}NODE;

NODE A[100100];
NODE tree[131072 * 2];
NODE MaxNode;

NODE isMin(NODE a, NODE b)
{
	if (a.value < b.value) return a;
	if (a.value == b.value && a.index < b.index) return a;

	return b;
}

NODE init(int left, int right, int node)
{
	if (left == right) return tree[node] = A[left];
	
	int mid = (left + right) / 2;

	return tree[node]
		= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}

NODE getMin(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return MaxNode;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	return isMin(getMin(left, mid, a, b, node * 2), getMin(mid + 1, right, a, b, node * 2 + 1));
}

NODE update(int left, int right, int node, int index, int value)
{
	if (index < left || right < index) return tree[node];
	if (left == right)
	{
		tree[node].value = value;

		return tree[node];
	}

	int mid = (left + right) / 2;
	NODE leftNode = update(left, mid, node * 2, index, value);
	NODE rightNode = update(mid + 1, right, node * 2 + 1, index, value);

	return tree[node] = isMin(leftNode, rightNode);
}

int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &A[i].value);
		A[i].index = i;
	}

	MaxNode.index = 0x7fff0000;
	MaxNode.value = 0x7fff0000;

	init(1, N, 1);

	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(1, N, 1, Ai, v);
		}
		else
		{
			NODE ans = getMin(1, N, 1, N, 1);

			printf("%d\n", ans.index);
		}
	}

	return 0;
}

---

바텀 업 세그먼트 트리는 다음과 같다.

update에서 node의 index를 초기화해야 하므로 treeIndex를 선언하여 index를 변경하지 않도록 하였다.

#include <stdio.h>

typedef long long int ll;

int N, M;

typedef struct st
{
	int index;
	int value;
}NODE;

NODE A[100100];
NODE tree[131072 * 2];
int start;
NODE MaxNode;

NODE isMin(NODE a, NODE b)
{
	if (a.value < b.value) return a;
	if (a.value == b.value && a.index < b.index) return a;

	return b;
}

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

	tree[treeindex].value = value;
	tree[treeindex].index = index;

	treeindex /= 2;

	while (treeindex > 1)
	{
		tree[treeindex] = isMin(tree[treeindex * 2], tree[treeindex * 2 + 1]);

		treeindex /= 2;
	}
}

NODE getMin(int left, int right)
{
	NODE ans;
	
	ans.value = 0x7fff0000;
	ans.index = 0x7fff0000;

	left += start;
	right += start;

	while (left < right)
	{
		if (left % 2 == 0) left /= 2;
		else
		{
			ans = isMin(ans, tree[left]);
			left += 1;
			left /= 2;
		}

		if (right % 2 == 1) right /= 2;
		else
		{
			ans = isMin(ans, tree[right]);
			right -= 1;
			right /= 2;
		}
	}

	if (left == right) ans = isMin(ans, tree[left]);

	return ans;
}

int main()
{
	int n;

	scanf("%d", &N);

	for (n = 1; (1 << n) <= N; n++);
	start = 1 << n;
	start--;

	for (int i = 1; i <= N; i++)
	{
		int value;
		
		scanf("%d", &value);
		
		update(i, value);
	}

	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(Ai, v);
		}
		else
		{
			NODE ans = getMin(1, N);

			printf("%d\n", ans.index);
		}
	}

	return 0;
}