구간 합 최대? 2

• 쿼리에서 구하는 값이 단순한 최대 부분합이 아니라, 부분합을 포함하는 복잡한 형태의 수식인 것 같아 보인다. 그러나 K'_i = U * K_i + V 로 치환하면 쿼리는 max(K'_i + … + K'_j - V) = max(K'_i + … + K'_j) - V 가 되어서 결국 최대 부분합에서 V를 뺀 값으로 단순화된다.
• 최대 부분합 쿼리는 일명 금광세그라는 테크닉으로 O(logn)에 계산 가능하다. 자세한 것은 링크 참조.
• 세그먼트 트리 구축에 O(n)이 걸리고, q개의 쿼리를 각각 O(logn)에 처리하므로. 총 시간복잡도는 O(n+qlogn)

"""Solution code for "BOJ 15561. 구간 합 최대? 2".

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

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, Q, U, V = [int(x) for x in sys.stdin.readline().split()]
    K = [int(x) for x in sys.stdin.readline().split()]
    segtree = segmenttree.SegmentTree(
        (((x := U * k_i + V), x, x, x) for k_i in K), merge)
    for _ in range(Q):
        C, A, B = [int(x) for x in sys.stdin.readline().split()]
        if C == 1:
            segtree.set(A - 1, ((x := U * B + V), x, x, x))
        else:
            print(segtree.query(A - 1, B)[2] - V)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree