수열과 쿼리 10 [BOJ 13557]

금광 세그를 연습하기에 매우 좋은 문제이다. 개인적으로 처음에는 아이디어 떠올리는 것이 어려웠기 때문에 풀이를 조금 읽다가 아이디어가 잡히면 남은 풀이는 혼자 완성해보는 것을 추천한다.

 

문제 요약

길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다.

x1 y1 x2 y2 : 구간 [x1, y1]에 속하는 모든 i와 구간 [x2, y2]에 속하는 모든 j(>=i)에 대해서 수열의 [i, j] 구간합의 최댓값을 출력한다.

 

사용 알고리즘

금광 세그

 

풀이

금광 세그를 구현하면 임의의 구간 [i, j]에서 수열의 prefix 최대합, suffix 최대합, 부분 최대 합, 전체 합을 O(logN)에 구할 수 있다. 각 값을 구간의 left, right, ans, all이라고 하자.

 

① [x1, y1]과 [x2, y2]가 겹치지 않는 경우

y1<x2인 경우이고, 이 때는 y1+1번째 원소부터 x2-1번째 원소는 자동으로 포함된다. 이는 [y1+1, x2-1]의 all로 계산한다.

이제 [x1, y1]에서는 오른쪽부터 합이 최대가 되게 골라주어야 하므로 해당 구간의 right를 취하고, [x2, y2]에서는 왼쪽부터 합이 최대가 되게 골라주어야 하므로 해당 구간의 left를 취한다.

세 수의 합이 답이다.

 

② [x1, y1]과 [x2, y2]가 겹치는 경우

y1>=x2인 경우이고, 이 때는 x2번째 원소부터 y1번째 원소는 시작점, 끝점으로 모두 가능하다.

설명의 편의를 위해 [x1, x2-1]을 구간 A, [x2, y1]을 구간 B, [y1+1,y2]을 구간 C라고 하자.

시작점과 끝점이 각 구간 A, B, C 중 어디에 속하는지에 따라 경우를 나눌 것이다.

:: (시작점, 끝점)=(A, B) / (B, C) / (A, C)인 경우

시작점과 끝점으로 가능한 위치가 서로 다른 구간에 속하는 경우이다.

①과 같은 경우이므로, 같은 방식으로 세 경우의 값을 모두 구할 수 있다.

:: (시작점, 끝점)=(B, B)인 경우

시작점과 끝점으로 가능한 위치가 같다.

즉, 구간 B 안에서 최대 부분합을 그대로 사용하면 된다.

 

이렇게 처리하면 모든 쿼리를 세그먼트 트리에 금광 세그 쿼리를 적절히 날려 해결해줄 수 있다. 금광 세그를 구현해 본 사람이라면 구현도 어렵지 않다.

전체 시간복잡도는 O((N+Q)logN)이 된다. 처리해야할 값도 많고 쿼리 당 금광 세그 쿼리를 여러 번 호출하여 상수가 좀 클 것으로 예상했는데, 208ms로 시간제한인 2초 안에 넉넉하게 들어온다. N과 Q가 모두 10만으로 그렇게 크지 않아서 가능한 것 같다.

 

코드

풀이에서 말한 구간 A, B, C는 코드에서 x, y, z라는 변수명으로 나타나있다.

#include<bits/stdc++.h>
#define SIZE 100010
using namespace std;
typedef long long ll;
struct st
{
    ll lft,rgt,ans,all;
};
ll N,M,A[SIZE];
st seg[SIZE<<2],zero={(ll)-1e18,(ll)-1e18,(ll)-1e18,0};
st mer(st x,st y)
{
    return {max(x.lft,x.all+y.lft),max(y.rgt,x.rgt+y.all),max(max(x.ans,y.ans),x.rgt+y.lft),x.all+y.all};
}
st init(int l,int r,int node)
{
    if(l==r)return seg[node]={A[l],A[l],A[l],A[l]};
    int mid=l+r>>1;
    return seg[node]=mer(init(l,mid,node<<1),init(mid+1,r,(node<<1)+1));
}
st query(int l,int r,int node,int s,int e)
{
    if(l>e||r<s)return zero;
    if(s<=l&&r<=e)return seg[node];
    int mid=l+r>>1;
    return mer(query(l,mid,node<<1,s,e),query(mid+1,r,(node<<1)+1,s,e));
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++)cin>>A[i];
    init(1,N,1);
    for(cin>>M;M--;){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        if(y1<x2)cout<<query(1,N,1,x1,y1).rgt+query(1,N,1,x2,y2).lft+query(1,N,1,y1+1,x2-1).all<<'\n';
        else{
            st x,y,z;
            x=query(1,N,1,x1,x2-1);
            y=query(1,N,1,x2,y1);
            z=query(1,N,1,y1+1,y2);
            ll ret=max(max(x.rgt+y.lft,y.rgt+z.lft),max(x.rgt+y.all+z.lft,y.ans));
            cout<<ret<<'\n';
        }
    }
}