BOJ 16993 : 연속합과 쿼리

• 문제 링크 : boj.kr/16993
• 난이도 : P1
• 태그 : 세그먼트 트리

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

template<typename T>
class segTree {
private:
    ll n;
    T id;
    T(*merge)(T, T);
    vector<T> tree;
public:
    segTree(ll n, T id, T(*merge)(T, T)) {
        this->n = n;
        this->id = id;
        this->merge = merge;
        tree.resize(n*4);
    }
    void update(ll idx, T value) {
        _update(1, 1, n, idx, value);
    }
    T query(ll l, ll r) {
        return _query(1, 1, n, l, r);
    }
private:
    void _update(int node, int s, int e, int idx, T value) {
        if(idx < s || e < idx) return;

        if(s == e) {
            tree[node] = value;
            return;
        }

        _update(node*2, s, (s+e)/2, idx, value);
        _update(node*2+1, (s+e)/2+1, e, idx, value);
        tree[node] = merge(tree[node*2], tree[node*2+1]);
    }
    T _query(int node, int s, int e, int l, int r) {
        if(l > e || r < s) return id;
        if(l <= s && e <= r) return tree[node];

        T lq = _query(node*2, s, (s+e)/2, l, r);
        T rq = _query(node*2+1, (s+e)/2+1, e, l, r);
        return merge(lq, rq);
    }
};

struct node {
    ll ls;
    ll rs;
    ll ms;
    ll ts;
    node operator+(const node& a) {
        node temp;
        temp.ls = max(ls, ts + a.ls);
        temp.rs = max(a.rs, a.ts + rs);
        temp.ms = max({ms, a.ms, rs+a.ls});
        temp.ts = ts + a.ts;
        return temp;
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    segTree<node> s(n, {-INF, -INF, -INF, 0}, [](node a, node b){return a+b;});
    for(int i = 1; i <= n; i++) {
        int input;
        cin >> input;
        s.update(i, {input, input, input, input});
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        cout << s.query(a, b).ms << "\n";
    }
    return 0;
}

---

풀이

두 구간 l, r을 합할 때 새로운 구간 A의 최대 부분구간합을 구하기 위해, 어떤 구간의 정보를 {왼쪽 끝부터 시작하는 최대 부분구간합, 오른쪽부터 시작하는 최대 부분구간합, 전체 구간의 최대 부분구간합, 전체 구간의 구간합}으로 각각 ls, rs, ms, ts로 정의한다.

A_ls = max(l_ls, l_ts+r_ls)

A_rs = max(r_rs, r_ts+l_rs)

A_ms = max(l_ms, r_ms, l_rs+r_ls)

A_ts = l_ts + r_ts

위와 같이 merge를 정의하여 특정 구간의 최대 부분 구간합을 구할 수 있다.