• 구간 합 최대? 2의 쉬운 버전. n과 q의 범위가 10^5에서 10^3으로 줄었다.
• 세그먼트 트리를 이용해서 O(n+qlogn)에 해결하는 정해는 구간 합 최대? 2를 참조. 코드도 그대로 복붙했다.
• 다만 문제에서 원래 의도한 풀이는, 그냥 K'_i = U*K_i+V로 치환하는 테크닉을 적용한 이후에, 매 쿼리마다 구간에서 최대 부분합을 구하는 것이었을것 같다. 최대 부분합 (Maximum subarray problem)을 그냥 푸는 것은, 카데인 알고리즘으로 O(n)에 가능하므로 O(nq)풀이가 가능하고, 아마 통과될 것이다 (구현은 안해봄)

"""Solution code for "BOJ 15560. 구간 합 최대? 1".

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

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