문제 링크

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

문제

시도 1

#include <iostream>

using namespace std;

int tree[400004] = { 0 };
int A[100001] = { 0 };

int init(int start, int end, int node) {
	if (start == end) { //구간이 없는 경우
		tree[node] = A[start]; //해당 값이 노드의 값이 된다.
		return tree[node]; //노드의 값 리턴
	}
	int mid = (start + end) / 2; //중간 인덱스
	int left = init(start, mid, node * 2); //왼쪽 자식 노드의 인덱스는 부모 노드의 2배
	int right = init(mid + 1, end, node * 2 + 1); //오른쪽 자식 노드의 인덱스는 부모 노드의 2배 + 1
	tree[node] = left * right; // 자식 노드의 곱이 부모 노드의 값
	return tree[node]; //노드의 값 리턴
}

int mul(int start, int end, int node, int left, int right) {
	//범위를 벗어나는 경우 
	if (left > end || right < start) {
		return 1; //1을 리턴하여 곱해도 영향이 없도록 한다.
	}
	//범위 내부인 경우
	if (left <= start && end <= right) {
		return tree[node]; //노드의 값 리턴
	}
	int mid = (start + end) / 2;
	// 왼쪽 노드의 해당하는 구간의 곱 * 오른쪽 노드의 해당하는 구간의 곱
	return mul(start, mid, node * 2, left, right) * mul(mid + 1, end, node * 2 + 1, left, right);
}

int update(int start, int end, int node, int index, int value) {
	//범위를 벗어나는 경우
	if (index > end || index < start) {
		return tree[node];
	}
	//해당 노드를 찾은 경우
	if (start == end) {
		tree[node] = value; //값 업데이트 
		return tree[node];//리턴
	}
	int mid = (start + end) / 2;
	//if (mid < index) { //오른쪽에 해당 인덱스가 있는 경우
	//	update(mid + 1, end, node * 2 + 1, index, value); //오른쪽 자식 노드에서 다시 찾기
	//}
	//else { //왼쪽에 해당 인덱스가 있는 경우
	//	update(start, mid, node * 2, index, value); //왼쪽 자식 노드에서 다시 찾기
	//}

	//tree[node] = tree[node * 2] * tree[node * 2 + 1]; //현재 노드는 자식 노드의 곱으로 업데이트
	return tree[node] = update(start, mid, node * 2, index, value) * update(mid + 1, end, node * 2 + 1, index, value);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (!cin.eof()) {
		int N, K;
		cin >> N >> K;
		for (int i = 0; i < N; i++) {
			int tmp;
			cin >> tmp;
			if (tmp > 0) {
				tmp = 1;
			}
			else if (tmp < 0) {
				tmp = -1;
			}
			A[i] = tmp;
		}

		init(0, N - 1, 1);
		for (int i = 0; i < K; i++) {
			char mode;
			int a, b;
			cin >> mode >> a >> b;
			if (mode == 'C') {
				if (b > 0) {
					b = 1;
				}
				else if (b < 0) {
					b = -1;
				}

				update(0, N - 1, 1, a - 1, b);
			}
			else if (mode == 'P') {
				int result = mul(0, N - 1, 1, a - 1, b - 1);
				if (result > 0) {
					cout << '+';
				}
				else if (result < 0) {
					cout << '-';
				}
				else {
					cout << '0';
				}
			}
		}
		cout << '\n';
	}

	return 0;
}

풀이

#include <iostream>
#include <vector>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, k;
vector<int> v, tree;

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

int init(int start, int end, int node) {
	if (start == end) {
		return tree[node] = convert(v[start]);
	}
	int mid = (start + end) / 2;
	return tree[node] = init(start, mid, node * 2) * init(mid + 1, end, node * 2 + 1);
	
}

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

int update(int start, int end, int node, int index, int num) {
	if (start > index || index > end) return tree[node];
	if (start == end) return tree[node] = convert(num);

	int mid = (start + end) / 2;
	return tree[node] =
		update(start, mid, node * 2, index, num) *
		update(mid + 1, end, node * 2 + 1, index, num);
}

int main() {
	fastio;
	while (cin >> n >> k) {
		v.resize(n);
		tree.resize(4 * n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		init(0, n - 1, 1);

		for (int i = 0; i < k; i++) {
			char op;
			int a, b;
			cin >> op >> a >> b;
			if (op == 'C') {
				update(0, n - 1, 1, a - 1, b);
			}
			else {
				int result = mul(0, n - 1, 1, a - 1, b - 1);
				if (result == 0) {
					cout << '0';
				}
				else if (result > 0) {
					cout << '+';
				}
				else {
					cout << '-';
				}
			}
		}
		cout << '\n';
	}




	return 0;
}

• 구간 곱 문제를 시간 안에 풀어야하기 때문에 세그먼트 트리 자료구조를 이용하여 해결해야한다.
• 구간 합 세그먼트 트리를 응용해서 문제를 해결해보았지만 틀렸습니다가 발생하였다.
• update 함수에서 발생한 오류인 것 같은데 정확한 오류를 찾지 못했다.