(C++) - 백준(BOJ) 5676번 : 음주 코딩

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

5676번: 음주 코딩

segent tree를 이용해 구간곱을 O(logN)만에 구하는 문제였습니다.

 

 

📕 풀이방법

 n이 10^5고 모든 원소가 범위의 최대인 100이라면 100^(10^5)이므로 단순 정수 자료형들로는 해결할 수 없습니다. 다행히 출력해야하는 것이 부호 또는 0이기 때문에 적절히 치환해준다면 범위 초과를 넘길 수 있습니다.

 

📔 입력 및 초기화

 1. n만큼 원소를 vector 변수 v에 입력 받습니다. 

 2. 이 후 각 구간의 곱들을 tree라는 vector형 변수에 넣습니다. 삽입시 v의 원소 그대로를 넣는 것이아닌 양수라면 1, 음수라면 -1, 0이라면 0을 넣어줍니다.

 

 

📔 풀이과정

 EOF일 때까지 입력받으면서 while loop를 수행합니다. 

 

 1. c라면 update 이 때 수 그대로를 해당 위치에 저장하는 것이 아닌 치환해서 저장해야 합니다.

 

 2. p라면 구간곱을 구한뒤 해당 부호를 출력해줍니다.

 

---

 

 

📕 Code

#include <bits/stdc++.h>
#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';
    }

}