[ BOJ ] 5676 : 음주 코딩 ( GOLD 1 ) / C

문제

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 수열의 크기 N과 게임의 라운드 수 K가 주어진다. (1 ≤ N, K ≤ 105)

둘째 줄에는 총 N개의 숫자 Xi가 주어진다. (-100 ≤ Xi ≤ 100)

다음 K개 줄에는 선영이가 내린 명령이 주어진다. 명령은 C 또는 P로 시작한다.

C로 시작하는 명령은 변경 명령이고, 그 다음에 i와 V가 주어진다. Xi를 V로 변경하는 명령이다. (1 ≤ i ≤ N, -100 ≤ V ≤ 100)

P로 시작하는 명령은 곱셈 명령이고, 그 다음에 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

각 테스트 케이스에 곱셈 명령은 항상 한 번 이상있다.

출력

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

풀이 과정

세그먼트 트리를 사용해 구간의 곱을 구했다. 수의 크기가 너무 커질 위험이 있고 마침 문제에서 부호만 출력하기 때문에,  노드에 부호만 넣어 세그먼트 트리를 만들었다.

#include <stdio.h>

int arr[1000001];
int tree[4000004];
char result[1000001];

int init(int start, int end, int idx) {
	if (start == end) {
		if (arr[start] > 0) tree[idx] = 1;
		else if (arr[start] < 0) tree[idx] = -1;
		else tree[idx] = 0;

		return tree[idx];
	}

	int mid = (start + end) / 2;
	tree[idx] = init(start, mid, idx * 2) * init(mid + 1, end, idx * 2 + 1);
	return tree[idx];
}

void update(int start, int end, int idx, int what, int value) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] = value;
		return;
	}
	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what, value);
	update(mid + 1, end, idx * 2 + 1, what, value);

	tree[idx] = tree[idx * 2] * tree[idx * 2 + 1];
}

int interval_mul(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return 1;
	if (left <= start && end <= right) return tree[idx];
	
	int mid = (start + end) / 2;
	return interval_mul(start, mid, idx * 2, left, right) * interval_mul(mid + 1, end, idx * 2 + 1, left, right);
}

int main(void) {
	int n, m;
	while (1) {
		int res = scanf("%d %d", &n, &m);
		if (res == EOF || res == '\0' || res == 0 || res == '\n') break;

		for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

		init(0, n - 1, 1);

		int res_cnt = 0; 
		for (int i = 0; i < m; i++) {
			char mode;
			int n1, n2;
			getchar();
			scanf("%c %d %d", &mode, &n1, &n2);

			if (mode == 'C') {
				int tmp = 0;
				if (n2 > 0) tmp = 1;
				else if (n2 < 0) tmp = -1;

				update(0, n - 1, 1, n1 - 1, tmp);
			}
			else {
				int res = interval_mul(0, n - 1, 1, n1 - 1, n2 - 1);
				if (res > 0) result[res_cnt++] = '+';
				else if (res < 0) result[res_cnt++] = '-';
				else result[res_cnt++] = '0';
			}
		}
		for (int i = 0; i < res_cnt; i++) printf("%c", result[i]);
		printf("\n");
	}
	return 0;
}