[BOJ 16993] 연속합과 쿼리

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

16993번: 연속합과 쿼리

KOI 중등부 역대급 난이도로 유명한 웰노운....(동어반복인가??)이면서 다이아급 문제인 금광을 풀고 싶어서, 그앞의 연습문제 쯤 될법한 연속합과 쿼리를 풀러 갔습니다.

전반적으로 금광의 하위호환이다 싶었는데, 그래도 이게 쉽다는 소리는 아닙니다() 쓰는 로직이 비슷할 거 같고 금광도 좌표압축만 해주고 여러가지 전처리 해주면 풀 수 있겠다는 자신감을 얻었습니다.

열심히 풀고 나니까 벌써 4시가 넘었네요 그래도 문제 고민해서 새벽 돼서 풀었을 때 희열은 엄청난 것 같습니다 ㅋㅋ

 

전반적인 풀이방법은 다음과 같습니다.

 

이 문제는 세그트리를 사용하는 문제인데, 여기서는 세그트리에 구간에서의 연속합 최댓값을 저장하면 될 거라고 생각했습니다.

그런데 최댓값만 저장하면 다음 세그트리를 업데이트할 때 문제가 생깁니다. 서로 붙은 두 구간에서 최댓값을 구하려면 단순히 왼쪽 최댓값+오른쪽 최댓값을 한다고 되는 게 아니라, 걸친경우와 그렇지 않은 경우 등등을 여러가지 생각해줘야 하니까 골치가 아플 수밖에 없습니다.

 

그렇기 때문에 구간마다 '왼쪽에서 시작한 부분합 중 최댓값', '오른쪽에서 끝나는 부분합 중 최댓값', '그냥 최댓값'을 저장시키고(그래서 세그트리 안에 리스트를 넣는 식으로 구현했습니다.)그리고 탐색할 때도 각각의 구간들을 돌면서 거기서 최댓값들을 구하는 식으로 구현했습니다.

 

파이썬 코드지만 파이썬으로는 TLE가 뜨고 Pypy로 돌려야 정답이 뜨네요.

 

import sys
input=sys.stdin.readline

class sgTree:
    def __init__(self,L):
        self.len=len(L)
        newL=[]
        for i in L:newL.append([i,i,i,i])
        self.tree=[[0,0,0,0]for i in range(self.len)]+newL
        for i in range(self.len-1, 0, -1):
            L1=self.tree[i]
            left=self.tree[2*i]
            right=self.tree[2*i+1]
            #0th:lsum 1st:rsum 2nd:tot 3rd:max
            L1[0]=max([left[0],left[2]+right[0]])
            L1[1]=max([right[1],right[2]+left[1]])
            L1[2]=left[2]+right[2]
            L1[3]=max([left[1]+right[0],left[3],right[3],L1[0],L1[1]])

    def res(self, now, start, end, l, r):
        if end<l or r<start:return[-1000000]*4
        if l<=start and end<=r:return self.tree[now]
        mid=(start+end)//2
        L1=self.res(now*2,start,mid,l,r)
        L2=self.res(now*2+1,mid+1,end,l,r)
        L=[]
        L.append(max(L1[0],L1[2]+L2[0]))
        L.append(max(L2[1],L2[2]+L1[1]))
        L.append(L1[2]+L2[2])
        L.append(max([L1[1]+L2[0],L1[3],L2[3],L[0],L[1]]))
        return L

n=int(input())
L=list(map(int,input().split()))
c=1
while c<n:c*=2
L+=[0]*(c-n)
s=sgTree(L)
for i in ' '*int(input()):
    l,r=map(int,input().split())
    print(s.res(1,1,c,l,r)[3])