BOJ 백준 5676 : 음주 코딩

시작하면서

　이번 문제는 세그먼트 트리(Segment Tree) 문제이다.

BOJ 5676 - 음주 코딩

​

문제 이해

​ 이 문제는 기본적인 세그먼트 트리 문제와 틀이 같다. 하지만 다음 두 가지를 주의해야 한다.

1. 답을 출력할 때에는 숫자와 관계 없이 양수, 음수, 0 인지에 대해서만 묻는다.
2. 수열의 크기가 10^5 이므로 다짜고짜 전부 곱해서 저장하면 100^(10^5) 곱해야 하므로 자료형이 감당이 안 된다.

​ 위 두 가지 이유로 이 문제는 인풋을 받을때 양수면 1로, 음수면 -1로 치환해서 사용한다. 만약 1과 -1이 아니었으면 0을 곱했다가 값을 바꾸어 줄 때 로직이 복잡해지겠지만 다행히 1과 -1이므로 무시하고 덧셈, 뺄셈 세그먼트 트리처럼 진행하면 답이 나온다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 1. 배열의 인덱스 번호는 1부터 시작
// 2. 왼쪽 자식은 2 * index
// 3. 오른쪽 자식은 2 * index + 1
int InitSegmentTree(vector<int>& arr, vector<int>& segmentTree, int node, int start, int end)
{
	// 현재 노드가 리프 노드인 경우, 배열의 그 원소를 가져야 함
	if (start == end)
		return segmentTree[node] = arr[start];

	int mid = (start + end) * 0.5f;

	int left = InitSegmentTree(arr, segmentTree, node * 2, start, mid);
	int right = InitSegmentTree(arr, segmentTree, node * 2 + 1, mid + 1, end);

	segmentTree[node] = left * right;

	return segmentTree[node];
}

int UpdateSegmentTree(vector<int>& segmentTree, int node, int start, int end, int index, int diff)
{
	// 1. [start, end]에 index가 포함되지 않는 경우
	if (start > index || end < index)
		return segmentTree[node];

	if (start == end)
		return segmentTree[node] = diff;

	// 리프 노드가 아닌 경우 자식도 변경해주어야 하기 때문에,
	// 리프 노드인지 검사를 하고 아래 자식 노드를 갱신해준다.
	int mid = (start + end) * 0.5f;

	int l = UpdateSegmentTree(segmentTree, node * 2, start, mid, index, diff);
	int r = UpdateSegmentTree(segmentTree, node * 2 + 1, mid + 1, end, index, diff);

	return segmentTree[node] = l * r;
}

int QuerySegmentTree(vector<int>& segmentTree, int node, int start, int end, int left, int right)
{
	// 1. [start, end] 앞 뒤에 [left, right]가 있는 경우
	if (left > end || right < start)
		return 1;

	// 2. [start, end]가 [left, right]에 포함되는 경우
	if (left <= start && end <= right)
		return segmentTree[node];

	// 3. 나머지 경우
	int mid = (start + end) * 0.5f;

	int l = QuerySegmentTree(segmentTree, node * 2, start, mid, left, right);
	int r = QuerySegmentTree(segmentTree, node * 2 + 1, mid + 1, end, left, right);
	int result = l * r;

	return result;
}

void ConvertValue(int* value)
{
	if (*value > 0)
	{
		*value = 1;
	}
	else if (*value < 0)
	{
		*value = -1;
	}
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<int> segmentTree;
	vector<int> numbers;
	int n, k;

	while (cin >> n)
	{
		cin >> k;

		segmentTree.resize(n * 4);
		numbers.resize(n + 1);
		for (int i = 1; i < n + 1; i++)
		{
			cin >> numbers[i];

			ConvertValue(&numbers[i]);
		}
		
		// make segment tree
		InitSegmentTree(numbers, segmentTree, 1, 1, n);

		for (int i = 0; i < k; i++)
		{
			char order;
			int v, w;

			cin >> order >> v >> w;

			if (order == 'C')
			{
				ConvertValue(&w);
				UpdateSegmentTree(segmentTree, 1, 1, n, v, w);
			}
			else if (order == 'P')
			{
				int result = QuerySegmentTree(segmentTree, 1, 1, n, v, w);

				if (result == 0)
				{
					cout << "0";
				}
				else if (result > 0)
				{
					cout << "+";
				}
				else
				{
					cout << "-";
				}
			}
		}
		cout << "\n";
	}

    return 0;
}