[백준oj] 5676번 음주코딩

www.acmicpc.net/problem/5676

5676번: 음주 코딩

---

1)세그먼트 트리를 변형하여 부분합을 부분곱으로 바꿔준뒤 계산을 해봤지만 실패.

 

2)왜 틀린지 보니 숫자 하나의 최대값=100, 최대 100000개의 숫자가 존재할 수 있으므로 최대 결과는 100의 100000승이 된다. 따라서 int범위를 넘어서니 long long, 하지만 long long범위도 담지 못해서 실패.

 

3)최악의 경우 long long 범위를 넘어가지만, 어차피 구해야될건, result값이 음수,양수,0인지 판별만 해주면 되니, 입력 혹은 교체를 할 때 양수/음수/0을 판별해서 1/-1/0 을 대신 넣어준 뒤, 부분 곱을 구하면 최종 결과값은 1/-1/0 이 나와서 int범위 내에 해결 가능하지만 시간초과

 

4)왜 그런지 찾고 찾으며 나온 해결책이 cout,cin의 속도문제 때문이라는 결론으로 인해 cin과 cout을 최적화 시켜준뒤 제출-> 해결

 

#define _CRT_SECURE_NO_WARNINGS
#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;
}