[ICPC] 백준 5676 - 음주 코딩

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

풀이

세트당 최대 10만개의 질의를 통해 구간 곱을 구하고 갱신하는 문제이다.

 

이를 처리하기 위해 세그먼트 트리를 생각해볼 수 있다. 다만 갱신하려는 구간에 0이 있는 경우 구간의 곱은 0이 되어 갱신할 때 어려움을 겪을 수 있다.

 

구간을 갱신할 때 먼저 리프 노드의 값을 바꿔주고 부모 노드에 이를 반영해주도록 하면 0이 포함된 구간은 문제 없이 처리할 수 있다.

 

문제에서는 값의 부호만 중요하므로 혹시 모를 오버플로우를 방지하기 위해 양수는 1, 음수는 -1로 통일하여 계산하도록 한다.

 

문제에서 요구하는 대로 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int ar[100001];
int n, k;

inline int mid(int stt, int end) { return stt + (end - stt) / 2; }

int init(vector<int> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = ar[start];
    int m = mid(start, end);
    return tree[node] = init(tree, node * 2, start, m) * init(tree, node * 2 + 1, m + 1, end);
}

int update(vector<int> &tree, int node, int start, int end, int idx, int diff)
{
    if (idx < start || idx > end) return tree[node];
    if (start == end) return tree[node] = diff;

    int m = mid(start, end);
    return tree[node] = update(tree, node * 2, start, m, idx, diff) * update(tree, node * 2 + 1, m + 1, end, idx, diff);
}

int query(vector<int> &tree, int node, int start, int end, int l, int r)
{
    if (l <= start && end <= r) return tree[node];
    if (start > r || end < l) return 1;
    int m = mid(start, end);
    return query(tree, node * 2, start, m, l, r) * query(tree, node * 2 + 1, m + 1, end, l, r);
}

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

    cin >> n >> k;

    while (!cin.fail())
    {
        string result("");
        vector<int> segtree(n * 4);

        for (int i = 1; i <= n; ++i)
        {
            int x;
            cin >> x;
            if (x > 0)
                x = 1;
            else if (x < 0)
                x = -1;
            ar[i] = x;
        }
            
        init(segtree, 1, 1, n);

        for (int i = 0; i < k; ++i)
        {
            char order;
            int a, b;
            cin >> order >> a >> b;

            if (order == 'C')
            {
                int diff = 0;
                if (b > 0)
                    diff = 1;
                else if (b < 0)
                    diff = -1;

                ar[a] = diff;
                update(segtree, 1, 1, n, a, diff);
            }
            else
            {
                int calc = query(segtree, 1, 1, n, a, b);
                if (!calc)
                    result.push_back('0');
                else if (calc > 0)
                    result.push_back('+');
                else
                    result.push_back('-');
            }   
        }

        cout << result << '\n';
        cin >> n >> k;
    }
}