티스토리 뷰

알고리즘 관련/BOJ

BOJ)5676 음주 코딩

JASON 자손9319 2017. 1. 10. 20:03

문제: icpc.me/5676


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
#define MAX_N 100000
using namespace std;
int seg[* 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 * + 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&&<= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid)*query(lo, hi, node * + 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, 111, n);
            else if (!y)
                update(i, 011, n);
            else
                update(i, -111, n);
        }
        for (int i = 0; i < k; i++) {
            getchar();
            scanf("%c%d%d"&x, &y, &z);
            if (x == 'C') {
                if (z > 0)
                    update(y, 111, n);
                else if (!z)
                    update(y, 011, n);
                else
                    update(y, -111, n);
            }
            else {
                int r = query(y, z, 11, n);
                if (!r)
                    printf("0");
                else
                    printf("%c", r > '+' : '-');
            }
        }
        puts("");
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1168 조세퍼스 문제2  (0) 2017.01.11
BOJ)9426 중앙값 측정  (7) 2017.01.11
BOJ)5676 음주 코딩  (0) 2017.01.10
BOJ)12016 라운드 로빈 스케줄러  (0) 2017.01.10
BOJ)3653 영화 수집  (0) 2017.01.10
BOJ)6549 히스토그램에서 가장 큰 직사각형  (0) 2017.01.10
댓글
댓글쓰기 폼