boj 16993 연속합과 쿼리

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

16993번: 연속합과 쿼리

"금광 세그" 라고 불릴 정도의 웰노운 문제지만 어렵습니다. ㅠㅠ

이 문제는 "금광" 문제를 풀기 위한 워밍업 문제이며, 이 문제를 푸셨다면 금광 문제에 도전하시는 것도 좋습니다.

 

금광 세그는 구간에서 가장 큰 연속합을 구하는 문제입니다.

세그먼트 트리를 활용할 수 있으며, 두 개의 노드를 병합했을 때,

[왼쪽 노드의 최대, 오른쪽 노드의 최대, 두 노드의 중간]

이 정도가 답이 될 수 있습니다.

 

이를 구하기 위해 세그먼트 트리에는 다음과 같은 값을 저장합니다.

• l: 왼쪽 하위노드 (leftNode)의 최대
• r: 오른쪽 하위노드 (rightNode)의 최대
• max: 현재 노드의 최대
• sum: 현재 노드의 전체 합

이 값들을 구하는 방법은

• l: max(leftNode.l, leftNode.sum + rightNode.l)
• r: max(rightNode.r, rightNode.sum + leftNode.r)
• max: max(leftNode.max, rightNode.max, leftNode.r + rightNode.l)
• sum: leftNode.sum + rightNode.sum

이러면 전체 구간에서의 max를 구할 수 있습니다.

 

해당 식을 알고 있다면 쉽게 풀리는 문제지만, 처음보는 입장에서 이해하기는 어려웠습니다.

비슷한 문제로 update가 추가된 문제와 좌표압축이 추가된 금광 문제도 함께 공유드리고, 마무리하겠습니다.

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

15561번: 구간 합 최대? 2

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

10167번: 금광

 

 

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
 
typedef struct Node {
    int l;
    int r;
    int max;
    int sum;
}Node;
 
Node tree[MAX * 4];
int list[MAX];
int N, M;
 
Node init(int node, int s, int e) {
    if (s == e) {
        return tree[node] = { list[s], list[s], list[s], list[s] };
    }
 
    int m = (s + e) / 2;
    Node leftNode = init(node * 2, s, m);
    Node rightNode = init(node * 2 + 1, m + 1, e);
    return tree[node] = { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, leftNode.r + rightNode.sum), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
 
Node query(int node, int s, int e, int l, int r) {
    if (s > r || l > e) return { (int)-1e9, (int)-1e9, (int)-1e9, 0 };
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    Node leftNode = query(node * 2, s, m, l, r);
    Node rightNode = query(node * 2 + 1, m + 1, e, l, r);
    return { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, leftNode.r + rightNode.sum), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
 
void func() {
    int l, r;
    cin >> M;
    while (M--) {
        cin >> l >> r;
        cout << query(1, 1, N, l, r).max << '\n';
    }
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    init(1, 1, N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}