TLE DP Round C 2020 Candies

candies.py

T = int(input())

# update function
def build_dp(N, A, dp1, dp2, start):
    # dp2 is the regular prefix sum

    if start == 0:
        dp1[0] = A[0]

        dp2[0] = A[0]
        l = 1

    else:
        l = start
    for i in range(l, N):
        dp1[i] = (-1)**(i) * A[i] * (i + 1) + dp1[i-1]

        dp2[i] = (-1)**(i) * A[i] + dp2[i-1]

def query_dp(dp1, dp2, l, r):

    dp1query = (dp1[r] - dp1[l-1]) if l > 0 else dp1[r]
    dp2query = (dp2[r] - dp2[l-1]) if l > 0 else dp2[r]

    res = dp1query - (l) * dp2query

    res = -res if l % 2 == 1 else res
    return res

for case in range(T):
    [N, Q] = list(map(int, input().split()))
    # Q is the number of ops (update or query)

    A = list(map(int, input().split()))

    dp1 = [A[0]] * N
    dp2 = [A[0]] * N

    build_dp(N, A, dp1, dp2, 0)
    res = 0

    for kx in range(Q):
        [op, fst, snd] = input().split()
        fst = int(fst)
        snd = int(snd)

        if op == 'Q':
            q = query_dp(dp1, dp2, fst-1, snd-1)
            # print(("wpp", fst, snd, q))
            res += q

        else:
            A[fst-1] = snd
            build_dp(N, A, dp1, dp2, fst-1)

    print("Case #{}: {}".format(case + 1, res))