Official

C - Sum of Min Query Editorial by en_translator


Among the \(N\) summands, only one value is affected by a query. Therefore, we can compute the delta and successively apply to the maintained answer.

Sample code (Python3)

import sys

input = sys.stdin.readline
n, q = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    ans += min(a[i], b[i])
for _ in range(q):
    cc, xx, vv = map(str, input().split())
    c, x, v = cc == "A", int(xx), int(vv)
    x -= 1
    ans -= min(a[x], b[x])
    if c:
        a[x] = v
    else:
        b[x] = v
    ans += min(a[x], b[x])
    print(ans)

posted:
last update: