import sys
input = sys.stdin.readline
def make(s,e,x):
if s==e:
seg[0][x]=seg[1][x]=prefix[s]
seg[2][x]=data[s-1]
return
mid = (s+e)//2
make(s,mid,x*2); make(mid+1,e,x*2+1)
seg[0][x] = min(seg[0][x*2],seg[0][x*2+1])
seg[1][x] = max(seg[1][x*2],seg[1][x*2+1])
seg[2][x] = max(seg[2][x*2],seg[2][x*2+1],seg[1][x*2+1]-seg[0][x*2])
def minmax(i,j,s,e,x,m):
if i==s and j==e:
return seg[m][x]
mid = (s+e)//2
if j<=mid:
return minmax(i,j,s,mid,x*2,m)
if i>mid:
return minmax(i,j,mid+1,e,x*2+1,m)
r1,r2 = minmax(i,mid,s,mid,x*2,m),minmax(mid+1,j,mid+1,e,x*2+1,m)
return max(r1,r2) if m else min(r1,r2)
def maxdif(i,j,s,e,x):
if i==s and j==e:
return seg[2][x]
mid = (s+e)//2
if j<=mid:
return maxdif(i,j,s,mid,x*2)
if i>mid:
return maxdif(i,j,mid+1,e,x*2+1)
return max(maxdif(i,mid,s,mid,x*2),maxdif(mid+1,j,mid+1,e,x*2+1),minmax(mid+1,j,mid+1,e,x*2+1,1)-minmax(i,mid,s,mid,x*2,0))
N = int(input())
data = [*map(int,input().split())]
prefix = [0]
for d in data:
prefix.append(prefix[-1]+d)
seg = [[0]*4*N for i in range(3)]
make(0,N,1)
for x1,y1,x2,y2 in [[*map(int,input().split())] for i in range(int(input()))]:
if y1<x2:
print(minmax(x2,y2,0,N,1,1)-minmax(x1-1,y1-1,0,N,1,0))
else:
print(max(minmax(y1,y2,0,N,1,1)-minmax(x1-1,y1-1,0,N,1,0),minmax(x2,y2,0,N,1,1)-minmax(x1-1,x2-1,0,N,1,0),maxdif(x2,y1,0,N,1)))
누적합 + 세그먼트 트리로 해결하였다.
이 문제는 두 가지 분기로 나눌 수 있다. y1이 x2보다 작은 경우(즉, i의 범위와 j의 범위가 겹치지 않는 경우)와 그렇지 않은 경우이다. i의 범위와 j의 범위가 겹치지 않을 때는 쉽게 해결할 수 있다.
1. 수열의 누적합을 구한다.
2. 누적합에 대한 min 세그트리와 max 세그트리를 만든다.
3. j의 범위에서의 최댓값 - i의 범위에서의 최솟값이 곧 결과값이다. (차이가 곧 부분수열의 합이므로)
문제는 i의 범위와 j의 범위가 겹칠때이다. x2~y1 사이에서 i,j가 둘 다 존재하는 경우를 고려해야하는데, 이 점이 까다로웠다. 이는 세그트리를 하나 더 생성하는 것으로 해결할 수 있었다.
코드에서 seg[0]은 minseg, seg[1]은 maxseg를 의미한다. 여기에 seg[2]를 추가하였고, seg[2]는 해당 구간에서의 최대 차잇값을 의미한다. 이를 구현하는 방법은,
1. 누적합에 대한 minseg와 maxseg를 만든다. (위에서 이미 실행)
2. maxdifseg는 해당 구간에서의 최대차이이다.
3. maxdif 세그에서, 현재 세그값은 구간의 중심인 mid를 기준으로 start~mid의 최솟값과 mid+1~end의 최댓값의 차이와 start~mid의 최대차이, mid+1~end의 최대차이 중 최댓값이다.
이와같이, i와 j의 범위가 겹쳐질 때와 그렇지 않을 때를 분기로 나누어 문제를 해결할 수 있다.
여담으로 이 문제는 금광세그와 비슷하다고 한다. 이 문제를 자력으로 풀었으니 금광도 자력으로 해결해봐야겠다.