반응형

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

 

11962번: Counting Haybales

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 세그먼트 트리를 업데이트 해줍니다.

 

2. 구간 합과 구간 최솟값을 각각 저장해 쿼리에 맞게 출력해줍니다.

 

[ 소스코드 ]

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#define ll long long
 
using namespace std;
 
struct node {
    ll sum;
    ll min;
};
 
int N, Q;
int arr[200001];
node segTree[524300];
ll lazy[524300];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node].sum += lazy[node] * (1LL * e - s + 1);
        segTree[node].min += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
 
    return;
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node].sum = 1LL * arr[s];
        segTree[node].min = 1LL * arr[s];
 
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int C)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node].sum += (1LL * e - s + 1) * (1LL * C);
        segTree[node].min += C;
 
        if (s != e) {
            lazy[node * 2] += C;
            lazy[node * 2 + 1] += C;
        }
 
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, C);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, C);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
ll getSum(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node].sum;
 
    int m = (s + e) / 2;
    
    return getSum(node * 2, s, m, sidx, eidx) + getSum(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
ll getMin(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 11111111111;
    if (sidx <= s && e <= eidx) return segTree[node].min;
 
    int m = (s + e) / 2;
 
    return min(getMin(node * 2, s, m, sidx, eidx), getMin(node * 2 + 1, m + 1, e, sidx, eidx));
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        char cmd;
        int A, B;
        cin >> cmd >> A >> B;
 
        if (cmd == 'M') {
            cout << getMin(1, 1, N, A, B) << '\n';
        }
        else if (cmd == 'P') {
            int C;
            cin >> C;
 
 
            updateTree(1, 1, N, A, B, C);
        }
        else {
            cout << getSum(1, 1, N, A, B) << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05

+ Recent posts

티스토리툴바