[BOJ 5676 // C++] 음주 코딩

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5676번 문제인 음주 코딩이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/5676

5676번: 음주 코딩

이 문제는 기본적인 세그먼트 트리(segment tree) 활용 문제이다.

양수는 1, 음수는 -1, 0은 그대로 0을 리프노드에 넣은 세그먼트 트리를 이용하면 간단히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;

int arr[100001];
int seg[262145];

int init(int L, int R, int sI) {
    if (L == R) seg[sI] = arr[L];
    else seg[sI] = init(L, (L + R) / 2, sI * 2) * init((L + R) / 2 + 1, R, sI * 2 + 1);
    return seg[sI];
}

void update(int L, int R, int val, int qI, int sI) {
    if (R < qI || qI < L) return;
    else if (L == R) seg[sI] = val;
    else {
        update(L, (L + R) / 2, val, qI, sI * 2); update((L + R) / 2 + 1, R, val, qI, sI * 2 + 1);
        seg[sI] = seg[sI * 2] * seg[sI * 2 + 1];
    }
}

int query(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 1;
    else if (qL <= L && R <= qR) return seg[sI];
    else return query(L, (L + R) / 2, qL, qR, sI * 2) * query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    while (cin >> N >> K) {
        for (int i = 1;i <= N;i++) {
            int x; cin >> x;
            if (x > 0) arr[i] = 1;
            else if (x < 0) arr[i] = -1;
            else arr[i] = 0;
        }
        init(1, N, 1);
        for (int i = 0;i < K;i++) {
            char X; cin >> X;
            if (X == 'C') {
                int a, b; cin >> a >> b;
                if (b > 0) b = 1;
                else if (b < 0) b = -1; // b==0이면 b=0
                update(1, N, b, a, 1);
            }
            else {
                int a, b; cin >> a >> b;
                int Q = query(1, N, a, b, 1);
                if (Q == 1) cout << '+';
                else if (Q == -1) cout << '-';
                else cout << '0';
            }
        }
        cout << '\n';
    }
    return 0;
    
}