ABC256F

ABC256F の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc256/submissions/32580103 (1534 ms)

問題

タイトル通り，数列Aの累積和Bの累積和Cの累積和Dを求める問題です．

解説

概要図です．

ABC256F_overview

概要図の内容は，公式解説（by kyopro_friends）を図解したものになります．
Dx = ... の式の導出は，公式解説を参照してください m(_ _)m．

この問題のポイントです．
Aの点更新は，Bの区間更新になり，
Bの点更新は，Cの区間更新になり，
Cの点更新は，Dの区間更新を意味するので，
愚直な実装では到底間に合いません．

そのため，A→B→C→Dが愚直に計算できないので，A→Dを直接計算できるような，第三の配列E, F, Gを用意することを考えます．

ただし，E, F, Gの第x項をクエリの度に累積和をとって，計算量O(N)で算出するようでは間に合わないので，区間和をO(logN)で算出できるBITを用います．

これは，Aの点更新にもO(logN)で計算できるので間に合います．
点更新をする際は，「a を v に置き換える」計算は，「a にv-a を足す」こと再現しています．

コードを提出リンクより参照できますが，あらゆるケースでBITをテストしているわけではなく，動作に確証がないので，もっと整備されたコードを各自参考にしてください．
m(_ _)m．

Parameters:

------------

bit0 : BITのクラス

     概要図の配列Exを計算するためのBIT．x=xのときのExの値は，変数e0．

bit1 : BITのクラス

     概要図の配列Fxを計算するためのBIT．x=xのときのFxの値は，変数e1．

bit2 : BITのクラス

     概要図の配列Gxを計算するためのBIT．x=xのときのGxの値は，変数e2．

class BasicBIT():
    """
    点更新のみBIT
    """
    ...(中略)...

MOD = 998244353
N, Q = map(int, input().split())
A = [0] + list(map(int, input().split()))  # 1-based indexing
bit0 = BasicBIT(A.copy())
bit1 = BasicBIT([a*i for i, a in enumerate(A)])
bit2 = BasicBIT([a*i*i for i, a in enumerate(A)])
for _ in range(Q):
    line = input()
    if line[0] == '1':
        _, x, v = map(int, line.split())
        a = bit0[x]
        bit0.add(x, v-a)
        bit1.add(x, x*(v-a))
        bit2.add(x, x*x*(v-a))
    if line[0] == '2':
        _, x = map(int, line.split())
        e0 = bit0.sum(x+1)
        e1 = bit1.sum(x+1)
        e2 = bit2.sum(x+1)
        ans = (e2 - (2*x+3)*e1 + (x+1)*(x+2)*e0)//2 % MOD
        print(ans)

以上，ABC256Fの解法でした．

＜参考解説リンク＞

・公式解説（by kyopro_friends）