백준 33949번: 🍕😋🤮 [C++]

작성일 | In
다이아몬드 V 다이아몬드 V

문제

🍕😋🤮
금광 세그 활용 문제입니다.

풀이

최대 부분 배열은 최소 부분 배열을 뺀 나머지로 생각할 수 있습니다. 최대 부분 배열이 $[S,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
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif

using namespace std;

using ll = long long;

constexpr ll INF = 1LL << 50;

template <typename node_t>
struct SegmentTree {
    vector<node_t> t;
    size_t size;
    SegmentTree(size_t length) : t() {
        size = 1 << ((int)ceil(log2(length)));
        t = vector<node_t>(size << 1);

        for (int i = size; i < size + length; i++)
            t[i] = node_t(0);
        for (int i = size - 1; i > 0; i--)
            t[i] = t[i << 1] + t[i << 1 | 1];
    }

    void add(int i, ll v) {
        t[i |= size] += v;
        for (i >>= 1; i > 0; i >>= 1)
            t[i] = t[i << 1] + t[i << 1 | 1];
    }
};

struct MaxNode {
    ll lmax = -INF, rmax = -INF, lrmax = -INF, sum = 0;

    MaxNode() = default;
    MaxNode(ll v) : lmax(v), rmax(v), lrmax(v), sum(v) {}

    void operator+=(ll v) {
        lmax += v;
        rmax += v;
        lrmax += v;
        sum += v;
    }

    MaxNode operator+(const MaxNode& node) {
        MaxNode ret;
        ret.lmax = max(lmax, sum + node.lmax);
        ret.rmax = max(rmax + node.sum, node.rmax);
        ret.lrmax = max({lrmax, rmax + node.lmax, node.lrmax});
        ret.sum = sum + node.sum;

        return ret;
    }
};
struct MinNode {
    ll lmin = INF, rmin = INF, lrmin = INF, sum = 0;

    MinNode() = default;
    MinNode(ll v) : lmin(v), rmin(v), lrmin(v), sum(v) {}

    void operator+=(ll v) {
        lmin += v;
        rmin += v;
        lrmin += v;
        sum += v;
    }

    MinNode operator+(const MinNode& node) {
        MinNode ret;
        ret.lmin = min(lmin, sum + node.lmin);
        ret.rmin = min(rmin + node.sum, node.rmin);
        ret.lrmin = min({lrmin, rmin + node.lmin, node.lrmin});
        ret.sum = sum + node.sum;

        return ret;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s, q;
    cin >> s >> q;

    SegmentTree<MaxNode> maxTree(s);
    SegmentTree<MinNode> minTree(s);
    while (q--) {
        int query;
        cin >> query;

        if (query == 1) {
            int a, b;
            cin >> a >> b;
            a--;

            maxTree.add(a, b);
            minTree.add(a, b);
        } else {
            if (minTree.t[1].sum == minTree.t[1].lrmin)
                cout << maxTree.t[1].lrmax << '\n';
            else
                cout << max(maxTree.t[1].lrmax,
                            minTree.t[1].sum - minTree.t[1].lrmin)
                     << '\n';
        }
    }
}

백준 33949번: 🍕😋🤮 [C++]