[백준oj] 5676번 음주코딩

www.acmicpc.net/problem/5676

5676번: 음주 코딩

---

 

간단한 세그먼트 트리구현 문제이다. 세그먼트트리 구간합을 구간 곱으로 적용을 해준다.

하지만 입력 받은 수 그대로 입력한다면, 오버플로우가 생길 수 있다. 문제에서 요구하는 출력은 음수인지 양수인지 0인지가 궁금한것이니 입력받을때 양수는1, 음수는 -1,0은 0으로 입력받아 구간곱으로 부호확인만 해주면된다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

long long tree[4*100001];

//초기화 겸 업데이트
int init(int st, int end, int node, int position,int value) {

	if (st > position || end < position) return tree[node];
		
	if (st == end) {
		return tree[node] = value;
	}

	int middle = (st + end)>>1;
	return tree[node] = init(st, middle, node * 2,position,value) * init(middle + 1, end, node * 2 + 1,position,value);
}

//구간 곱 구하는부분
int mul(int st, int end, int node, int l, int r) {
	//범위 밖이면 곱이니 1 리턴
	if (end < l || r < st) {
		return 1;
	}

	//범위안이면 해당 곱 리턴
	if (l <= st && end <= r) {

		return tree[node];
	}

	int middle = (st + end)>>1;
	return mul(st, middle, node * 2, l, r) * mul(middle + 1, end, node * 2 + 1, l, r);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n, k;
	char op;
	int a, b;
	int result;
	
	while(cin>>n>>k){
		int d;
		for (int i = 0; i < n; i++) {
			cin>>d;
			if (d > 0) init(0, n - 1, 1, i,1);
			else if (d < 0) init(0, n - 1, 1,i, -1);
			else init(0, n - 1, 1,i, 0);
		}
		for (int j = 0; j < k; j++) {
			cin >> op>>a>>b;
			if (op == 'C') {
				if (b > 0) init(0, n - 1, 1,a-1, 1);
				else if (b < 0) init(0, n - 1, 1,a-1, -1);
				else init(0, n - 1, 1, a-1,0);
			}
			else {
				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;
}