BOJ)5676 음주 코딩

문제: icpc.me/5676

값의 갱신이 일어날 때 i~j까지 모든 수를 곱했을 때 음수인지 양수인지 0인지 판단하는 프로그램을 작성하는 문제이다. 

음수인지 양수인지 0인지만 판단하면 되므로 세그먼트 트리를 이용한 구간 곱으로 쉽게 구할 수 있다.

입력된 수가 양수일 경우 1 음수일 경우 -1 0일 경우 0으로 값을 갱신해주며 쿼리에 따른 값을 출력해 주면 된다.

#include <cstdio>
#include <algorithm>
#define MAX_N 100000
using namespace std;
int seg[4 * MAX_N], n, k, a[MAX_N + 1], y, z;
char x;
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid)*update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 1;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid)*query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    while (scanf("%d%d", &n, &k) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &y);
            if (y > 0)
                update(i, 1, 1, 1, n);
            else if (!y)
                update(i, 0, 1, 1, n);
            else
                update(i, -1, 1, 1, n);
        }
        for (int i = 0; i < k; i++) {
            getchar();
            scanf("%c%d%d", &x, &y, &z);
            if (x == 'C') {
                if (z > 0)
                    update(y, 1, 1, 1, n);
                else if (!z)
                    update(y, 0, 1, 1, n);
                else
                    update(y, -1, 1, 1, n);
            }
            else {
                int r = query(y, z, 1, 1, n);
                if (!r)
                    printf("0");
                else
                    printf("%c", r > 0 ? '+' : '-');
            }
        }
        puts("");
    }
    return 0;
}