このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
何となく皆さん予想がついているとは思いますが、地殻変動が起こるたびに全ての区画の不便さを再計算していたら余裕でTLEです。
ここで、地殻変動が起こる際、不便さがどのように変化するのか確認してみましょう。
区画が5つ：1,4,7,2,8 地殻変動が2,4の範囲で+3だけ起こった場合を考えてみます。
ご覧いただいた通り、不便さが変わるのは地殻変動が起こった区画の左側と右側のみとなります。
この事を利用して、
①初めに不便さの合計を計算しておく
②地殻変動が起こる度に区画の左側と右側の不便さの変化を計算、それを①に反映する
といった手順で各地殻変動後の不便さ合計を求めていきます。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N, Q = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
# 右隣の区画との差の配列を作成
B = [A[i + 1] - A[i] for i in range(N - 1)] + [0] # 一番右の区画用に[0]を足しておく
# 不便さ合計初期値
ans = sum(abs(b) for b in B)
# 地殻変動ごとの不便さの差分を計算→合計に反映して出力
for _ in range(Q):
l, r, v = map(int, input().split(" "))
l, r = l - 1, r - 1
# 地殻変動前の左右の不便さ合計
before = abs(B[l - 1]) + abs(B[r]) # インデックスに注意
# 左側の階差の変化（+vだけ変化する）
if l != 0: # 1番目の区画以外の時のみ計算する
B[l - 1] += v
# 右側の階差の変化（-vだけ変化する）
if r != N - 1: # N番目の区画以外の時のみ計算する
B[r] -= v
# 地殻変動後の左右の不便さ合計
after = abs(B[l - 1]) + abs(B[r])
ans += after - before
print(ans)
if __name__ == '__main__':
main()
