사용자 도구

사이트 도구


ps:problems:boj:13557

수열과 쿼리 10

ps
링크https://www.acmicpc.net/problem/13557
출처BOJ
문제 번호13557
문제명수열과 쿼리 10
레벨플래티넘 1
분류

구간 쿼리

시간복잡도O(n+mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python
제출기록68948KB / 5460ms
최고기록5460ms
해결날짜2021/03/23

풀이

  • l과 r의 위치에 제약이 추가된 부분합의 형태인데.. 일반적인 부분합을 구하기 위해서 필요한 4가지 대푯값들, 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()

토론

댓글을 입력하세요:
T H᠎ T M᠎ T
 
ps/problems/boj/13557.txt · 마지막으로 수정됨: 2021/04/30 15:17 저자 teferi