[BOJ 16993] 연속합과 쿼리

Link

문제 링크

Problem

길이가 N인 수열 $A_1$, $A_2$, ..., $A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• $i~j$ : $A_i,~A_{i+1},~...,~A_j$에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N)

수열의 인덱스는 1부터 시작한다.

연속합은 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이며, 수는 한 개 이상 선택해야 한다.

Solution Part I

대충 구간에 대한 쿼리를 다루니, 세그먼트 트리가 제일 유력하다.

물론, 플래티넘 2의 특성 상 Mo’s algorithm이 판을 치는 단계라지만.. 이건 뭐 구간을 나누어서 따로따로 처리하는 그런 문제는 아닌 듯 하니 Query를 sort하여 푸는 문제는 아닌 듯 하다..

가장 쉽게 생각할 수 있는 방법은 $i$에서 $j$까지 중 가장 큰 부분합을 구하고, 그 때의 index를 $k$라 할 때 $i$에서 $k$까지의 부분합 중 최소를 구하여서 빼는 것이다만… 조금만 생각해보면 최선의 방법이 아님을 알 수 있다.

따라서, 다른 방법을 생각해야한다.

Solution Part II

이런 문제는 분할 정복을 통하여 처리한다.

결국은 $i$에서 $j$까지의 부분합의 최대는 세 가지 부분에서 나오기 마련이다.

1. $i$에서 시작하여 $k\ (k\leq j)$에서 끝이 나는 부분합

2. $k\ (1\leq k\leq j)$에서 시작하여 $j$에서 끝이 나는 부분합

3. 중간에서 시작하여 중간에서 끝나는 부분합

따라서 우리는 세그먼트 트리에

1. 가장 왼쪽에서 시작했을 때의 최대의 부분합

2. 가장 오른쪽으로 끝날 때의 최대의 부분합

3. 1번과 2번을 포함한 그냥 구간 내에서의 부분합

을 담고, 부모 노드의 업데이트는

1. 가장 왼쪽 부분합은 왼쪽 노드의 왼쪽 부분합과 왼쪽 노드 전체의 값 + 오른쪽 노드의 왼쪽 부분합 중 더 큰 값을 고르면 된다.

2. 가장 오른쪽의 부분합은 오른쪽 노드의 오른쪽 부분합과 오른쪽 노드 전체의 값 + 왼쪽 노드의 오른쪽 부분합 중 더 큰 값을 고르면 된다.

마지막 3번 같은 경우 생각을 잘 해야하는데, 최대 부분합은 왼쪽에서 나오거나, 오른쪽에서 나오거나, 둘 다 가지고 있거나이다.

둘 다 가지고 있을려면 왼쪽구간과 오른쪽 구간을 동시에 아울러야하고, 이 말은 즉슨 왼쪽 노드의 오른쪽으로 끝날 때의 최대 부분합(left node의 2번)과 오른쪽 노드의 왼쪽에서 시작했을 때의 최대 부분합(right node의 1번)을 합친 것이 최대의 구간합이 된다.

Solution Part III

Update는 큰 문제가 없으나, 값을 구할 때는 만약 포함되지 않는 구간에서 node를 가져올 경우 될 수 없는 값(e.g. -1234567890)과 같은 쓰레기값을 이용하여 Reset 해주어야 한다.

그 외에는 전부 segment tree의 implemention을 활용하면 된다.

Code

#include <bits/stdc++.h>
using namespace std;
#define MIN -100000005

struct seg{
    int tot, lef, rig;
    seg() : tot(0), lef(0), rig(0) {}
    seg(int tot, int lef, int rig) : tot(tot), lef(lef), rig(rig) {}
};
seg tree[400006];
int ps[100006];

seg update(int st, int en, int nd, int ch, int val) {
    if(ch < st || en < ch) return tree[nd];
    if(st == en) return tree[nd] = {val, val, val};
    seg left = update(st, (st+en)/2, nd * 2, ch, val);
    seg right = update((st+en)/2+1, en, nd*2+1, ch, val);
    tree[nd].lef = max(left.lef, right.lef + ps[(st+en)/2] - ps[st-1]);
    tree[nd].rig = max(right.rig, left.rig + ps[en] - ps[(st+en)/2]);
    tree[nd].tot = max(left.tot, max(right.tot, left.rig + right.lef));
    return tree[nd];
}

seg ans(int st, int en, int rst, int ren, int nd) {
    if(en < rst || ren < st) return seg(MIN, MIN, MIN);
    if(rst <= st && en <= ren)  return tree[nd];   
    seg left = ans(st, (st+en)/2, rst, ren, nd * 2);
    seg right = ans((st+en)/2+1, en, rst, ren, nd * 2 + 1);
    seg tmp;
    tmp.lef = max(left.lef, right.lef + ps[(st+en)/2] - ps[st-1]);
    tmp.rig = max(right.rig, left.rig + ps[en] - ps[(st+en)/2]);
    tmp.tot = max(left.tot, max(right.tot, left.rig + right.lef));
    return tmp;
}

int main() {
    int n, a[100006];
    scanf("%d", &n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        ps[i] = ps[i-1] + a[i];
        update(1, n, 1, i, a[i]);
    }
    // for(int i=1;i<=n;i++) update(1, n, 1, i, a[i]);   
    // for(int i=1;i<=4*n;i++) printf("%d %d %d\n", tree[i].tot, tree[i].lef, tree[i].rig);
    int q;
    scanf("%d", &q);
    while(q--) {
        int st, en;
        scanf("%d %d",&st, &en);
        printf("%d\n", ans(1, n, st, en, 1).tot);
    }
    return 0;
}

Uploaded by N2T