[자료구조] 백준 5676번: 음주 코딩 (C++)

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

5676번: 음주 코딩

이번 문제는 테스트 케이스가 몇 개인지 제한이 없고, 몇 개인지 주어지지도 않아서 이 부분을 참고해야 했다.

while (cin >> n >> k) { // 입력이 계속 들어오는 동안 (?)
	// 코드
}

이 부분에 집중하느라 50%에서 계속 틀렸어서 입력 부분이 문제인 걸까 생각해봤지만 조금만 생각했다면 이유를 찾을 수 있었다.

우선 이번 세그먼트 트리에서 나는 구간 곱을 넣으려 했었다. 하지만 모든 수열의 크기가 (10^5)가 최대고 들어갈 수 있는 값이 -100 <= Ai <= 100 사이인데 10^5 크기의 수열에 100이 다 들어가 있다면 구간 곱을 구하는 데에 있어서 따로 나머지 정리를 해주는 것도 아니라서 이를 감당해낼 자료형이 없었다.

그래서 문제를 보면

• 양수: 1
• 0: 0
• 음수: 0

으로 출력하라고 되어있다. 이 부분이 포인트다. 구간 곱이 양수라면 1을 저장하고, 음수라면 -1, 0이라면 0의 방식으로 저장하면 자료형에 붙잡히지 않고, 구현할 수 있었다.

그래서 업데이트, 쿼리, 세그먼트 트리 초기화 과정에서 다음 함수를 구현해서 사용해야 했다.

int convert(int value) {
	if (value > 0) return 1;
	else if (value < 0) return -1;
	else return 0;
}

구간 곱과 다르게 신경 써줄 부분은 굳이 뽑자면 update 부분이었다.

leaf 노드에 도달해서 새로운 value를 집어넣어야 할 때, convert를 시키면서 들어오게 하는 것.

int convert(int value) {
	if (value > 0) return 1;
	else if (value < 0) return -1;
	else return 0;
}

[AC 코드]

#include <iostream>
#include <vector>
#define MAX (100000 + 1)
#define ll long long
using namespace std;

ll arr[MAX];
ll sgTree[MAX * 4];
int T, n, k;

int convert(int value) {
	if (value > 0) return 1;
	else if (value < 0) return -1;
	else return 0;
}

ll sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = convert(arr[start]);
	}
	int mid = (start + end) / 2;
	return sgTree[node] = convert(sgInit(start, mid, node * 2) 
		* sgInit(mid + 1, end, node * 2 + 1));
}

ll update(int start, int end, int node, int idx, ll value) {
	if (idx > end || idx < start) return sgTree[node];
	if (start == end) return sgTree[node] = convert(value);
	int mid = (start + end) / 2;
	return sgTree[node] = convert(update(start, mid, node * 2, idx, value) * 
		update(mid + 1, end, node * 2 + 1, idx, value));
}

ll query(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 1;
	if (left <= start && right >= end) return sgTree[node];
	int mid = (start + end) / 2;
	return convert(query(start, mid, node * 2, left, right) * 
		query(mid + 1, end, node * 2 + 1, left, right));
}

int main() {
	
	while (cin >> n >> k) {
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}
		sgInit(1, n, 1);
		vector<char> result;
		for (int i = 0; i < k; i++) {
			char a;
			cin >> a;
			if (a == 'C') {
				int b;
				ll c;
				cin >> b >> c;
				update(1, n, 1, b, c);
			}
			else {
				int b, c;
				cin >> b >> c;
				ll value = query(1, n, 1, b, c);
				if (value > 0) result.push_back('+');
				else if (value == 0) result.push_back('0');
				else result.push_back('-');
			}
		}
		for (int i = 0; i < result.size(); i++) cout << result[i];
		cout << '\n';
		for (int i = 1; i <= n; i++) {
			arr[i] = 0;
		}
		for (int i = 1; i <= 4 * n; i++) {
			sgTree[i] = 0;
		}
	}
	return 0;
}
// 100 ^ 1000000