수열과 쿼리 10

• 부분합 쿼리(금광세그)의 응용.
• l과 r의 위치에 제약이 추가된 부분합의 형태인데.. 일반적인 부분합을 구하기 위해서 필요한 4가지 대푯값들, lmax, rmax, max, all 을 잘 조합해서 요구하는 값을 구할 수 있다.
  • 각 구간에 대해서 lmax, rmax, max, all 을 계산하는 것은 부분합 쿼리(금광세그)참고
• x2가 y1보다 큰지 작은지에 따라서 계산 방법이 나뉜다.
• x1≤y1≤x2≤y2인 경우에는. l과 r은 각각의 양쪽 끝에서만 위치가 바뀌고, 그와 관계 없이 [y1, x1]의 구간은 전부 포함된다. 그래서 최대 부분합은 [x1,y1).rmax + [y1,x2].all + (x2,y1].lmax 과 같이 계산된다
• x1≤x2≤y1≤y2인 경우에는 좀더 복잡하다. [x1,x2), [x2,y1], (y1,y2]를 각각 LEFT, MID, RIGHT라고 부르자. 가능한 경우의 수는 1) l∈LEFT and r∈MID, 2) l∈MID and r∈RIGHT, 3) l∈LEFT and r∈RIGHT, 4) l∈MID and r∈MID 의 네가지이다.
  • 이 4가지 경우의 최대 부분합은 각각 1) LEFT.rmax + MID.lmax, 2) MID.rmax + RIGHT.lmax, 3) LEFT.rmax + MID.all + RIGHT.lmax, 4) MID.max 이다. 이 4가지중 최댓값이 답이 된다.
• 결국 각 쿼리에 대해서, 세그먼트 트리의 구간값을 3개의 구간에 대해서 찾아서 조합하면 된다. 결국, O(logn).
• 세그먼트 트리 구축에 O(n), m개의 쿼리를 각 O(logn)에 처리하는 데에 O(mlogn). 총 시간복잡도는 O(n+logm)

"""Solution code for "BOJ 13557. 수열과 쿼리 10".

- Problem link: https://www.acmicpc.net/problem/13557
- Solution link: http://www.teferi.net/ps/problems/boj/13557
"""

import sys
from teflib import segmenttree


def merge(l, r):
    l_lmax, l_rmax, l_max, l_all = l
    r_lmax, r_rmax, r_max, r_all = r
    return (max(l_lmax, l_all + r_lmax), max(r_rmax, l_rmax + r_all),
            max(l_max, r_max, l_rmax + r_lmax), l_all + r_all)


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]
    segtree = segmenttree.SegmentTree(((x, x, x, x) for x in A), merge)
    M = int(sys.stdin.readline())
    for _ in range(M):
        x1, y1, x2, y2 = [int(x) for x in sys.stdin.readline().split()]
        if y1 <= x2:
            l_rmax = max(0, segtree.query(x1 - 1, y1 - 1)[1]) if x1 < y1 else 0
            m_all = segtree.query(y1 - 1, x2)[3]
            r_lmax = max(0, segtree.query(x2, y2)[0]) if x2 < y2 else 0
            print(l_rmax + m_all + r_lmax)
        else:
            l_rmax = max(0, segtree.query(x1 - 1, x2 - 1)[1]) if x1 < x2 else 0
            m_lmax, m_rmax, m_max, m_all = segtree.query(x2 - 1, y1)
            r_lmax = max(0, segtree.query(y1, y2)[0]) if y1 < y2 else 0
            print(max(l_rmax + m_lmax, 
                      m_rmax + r_lmax, 
                      l_rmax + m_all + r_lmax, 
                      m_max))


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree