반응형

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

 

5676번: 음주 코딩

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 구간 합 대신 구간 곱을 return 합니다.

 

2. 구간 곱의 부호만 판단하면 되므로 입력받은 값이 양수이면 1, 음수이면 -1로 저장합니다.

 

[ 소스코드 ]

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstring>
#include<vector>
 
using namespace std;
 
int N, K;
int arr[100001];
int segTree[263000];
vector<char>ans;
 
int invert(int num)
{
    if (num > 0) return 1;
    else if (num < 0) return -1;
    return 0;
}
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = left * right;
}
 
int changeTree(int node, int start, int end, int idx, int V)
{
    if (idx < start || end < idx) return segTree[node];
    if (start == end) return segTree[node] = V;
 
    int mid = (start + end) / 2;
    int left = changeTree(node * 2, start, mid, idx, V);
    int right = changeTree(node * 2 + 1, mid + 1, end, idx, V);
 
    return segTree[node] = left * right;
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (start > eidx || end < sidx) return 1;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left * right;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (cin >> N >> K) {
        memset(segTree, 0, sizeof(segTree));
        ans.clear();
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            arr[i] = invert(arr[i]);
        }
 
        makeTree(1, 1, N);
 
        for (int k = 0; k < K; k++) {
            char ch;
            cin >> ch;
 
            if (ch == 'C') {
                int i, V;
                cin >> i >> V;
 
                V = invert(V);
                changeTree(1, 1, N, i, V);
                arr[i] = V;
            }
            else {
                int i, j;
                cin >> i >> j;
 
                int temp = getTree(1, 1, N, i, j);
 
                if (temp < 0) ans.push_back('-');
                else if (temp > 0) ans.push_back('+');
                else ans.push_back('0');
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i];
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12

+ Recent posts

티스토리툴바