백준 5676번 음주 코딩 C++ 세그먼트 트리

리뷰

누적곱을 활용한 응용문제

 

문제 풀이

1. n개의 수를 입력받아 트리형태로 build 해주고, k에 줄로 입력되는 쿼리를 처리해 주어야 한다.
2. n은 최대 10만, 입력되는 숫자의 범위는 -100 ~ 100 이므로 누적곱을 해버리면 long long 타입으로 감당되지 않는다.
3. 따라서 입력을 받을 때 0이라면 0으로, 양수면 1, 음수면 -1로 변환 후 저장해 주어야 한다.
4. 이후 업데이트 시에도 value 값에 동일한 조건을 추가해 준다.
5. 마찬가지로 쿼리를 통해 반환받은 값을 0과 음수, 양수로 나누어 출력을 해준다.

 

참고 사항

누적곱 세그먼트 트리 로직은 같다, 입력과 출력에 신경을 써주면 되는 문제

 

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, k;
vector<int> tree;

void build(vector<int>& lst, int node, int start, int end) {
	if (start == end) tree[node] = lst[start];
	else {
		int mid = (start + end) / 2;
		build(lst, node * 2, start, mid);
		build(lst, node * 2 + 1, mid + 1, end);
		tree[node] = tree[node * 2] * tree[node * 2 + 1];
	}
}

void update(int node, int start, int end, int idx, int val) {
	if (start == end) tree[node] = val;
	else {
		int mid = (start + end) / 2;
		if (start <= idx && idx <= mid) update(node * 2, start, mid, idx, val);
		else update(node * 2 + 1, mid + 1, end, idx, val);
		tree[node] = tree[node * 2] * tree[node * 2 + 1];
	}
}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	while (cin >> n >> k) {
		vector<int> lst(n);
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			if (temp == 0) lst[i] = temp;
			else if (temp > 0) lst[i] = 1;
			else lst[i] = -1;
		}
		tree.resize(4 * n);
		build(lst, 1, 0, n - 1);

		while (k--) {
			char order;
			int a, b;
			cin >> order >> a >> b;
			if (order == 'C') {
				if (b == 0);
				else if (b > 0) b = 1;
				else b = -1;
				update(1, 0, n - 1, a - 1, b);
			}
			else {
				int num = query(1, 0, n - 1, a - 1, b - 1);
				if (num == 0) cout << 0;
				else if (num > 0) cout << '+';
				else cout << '-';
			}
		}
		cout << "\n";
	}
}