음주 코딩

문제 링크

음주 코딩

아이디어

• 특정 구간의 곱의 결과가 음수인지 양수인지 0인지 판단하는 문제
• \(1 \leq N, K \leq 10^5\) 의 범위 (\(N = \textrm{배열의 크기}, K = \textrm{쿼리의 수}\))
• 쿼리 당 \(O(logN)\) 이하의 시간복잡도를 요구
  • 구간 정보를 이용한 쿼리를 \(O(logN)\) 시간에 처리하기 위해서 세그먼트 트리를 이용
• 특정 구간에서 곱의 결과가 -, +, 0 인지 판단하기 위해서는 구간 내에서 음수의 개수와 0의 개수를 파악하는 것이 중요하다.
  • 특정 구간의 대표정보를 Pair 형태로 저장
  • {음수의 개수, 0의 개수}

소스 코드

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
namespace seg {
    pair<int,int> tree[500001];

    pair<int,int> init(int node, int l, int r) {
        if (l == r) {
            pair<int,int> res = {0, 0};
            if (v[l] < 0) {
                res.first++;
            } else if (v[l] == 0) {
                res.second++;
            }
            return tree[node] = res;
        }
        int m = (l + r) / 2;
        pair<int,int> left = init(node * 2, l, m);
        pair<int,int> right = init(node * 2 + 1, m + 1, r);
        return tree[node] = {left.first + right.first, left.second + right.second};
    }

    pair<int,int> query(int node, const int l, const int r, int tl, int tr) {
        if (l <= tl && tr <= r) {
            return tree[node];
        }
        if (r < tl || tr < l) {
            return {0, 0};
        }
        int tm = (tl + tr) / 2;
        pair<int,int> left = query(node * 2, l, r, tl, tm);
        pair<int,int> right = query(node * 2 + 1, l, r, tm + 1, tr);
        return {left.first + right.first, left.second + right.second};
    }

    pair<int,int> mutate(int node, const int tgt, const int value, int tl, int tr) {
        if (tgt < tl || tgt > tr) {
            return tree[node];
        }
        if (tl == tr) {
            pair<int,int> res = {0, 0};
            v[tl] = value;
            if (v[tl] < 0) {
                res.first++;
            } else if (v[tl] == 0) {
                res.second++;
            }
            return tree[node] = res;
        }
        int tm = (tl + tr) / 2;
        pair<int,int> left = mutate(node * 2, tgt, value, tl, tm);
        pair<int,int> right = mutate(node * 2 + 1, tgt, value, tm + 1, tr);
        return tree[node] = {left.first + right.first, left.second + right.second};
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, K;
    while (cin >> N >> K) {
        v.resize(N);
        for (auto &elem : v) cin >> elem;
        seg::init(1, 0, N - 1);

        for (int i = 0; i < K; i++) {
            char c;
            int arg1, arg2;
            cin >> c >> arg1 >> arg2;

            if (c == 'C') {
                // mutate
                arg1--;
                seg::mutate(1, arg1, arg2, 0, N - 1);
            } else if (c == 'P') {
                // query
                arg1--, arg2--;
                pair<int,int> res = seg::query(1, arg1, arg2, 0, N - 1);
                if (res.second > 0) {
                    cout << '0';
                } else if (res.first & 1) {
                    cout << '-';
                } else if (res.first % 2 == 0) {
                    cout << '+';
                }
            }
        }
        cout << '\n';
    }

    return 0;
}