競プロ典型 90 問：064 - Uplift（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/27
• 結果：解けた
• 時間：1時間ぐらい

考えたこと

• 各区画の標高を持つのはTLE。
• 各クエリ時点での不便さを更新していくようなアルゴリズムでないと、計算量的に間に合わなそう
• 左隣の標高との差を保持するのが良いかも。標高差をとすると、 を合計すれば答えになる。
• ただし、それだと各クエリで かかると、TLEするので、なにか工夫が必要そう。
• 最初に不便さを求めておけば、各クエリでの更新されるのは2箇所だけなので、その部分について不便さの差分を計算できそう。

公式解説

https://twitter.com/e869120/status/1403483256234799105/photo/1

解説を読んだふりかえり

• 考え方はあっていたので良かった。こういうのは階差と呼ぶらしい。
• もう少し早く検討、実装ができたら良かったなぁ。。。
• 解けたけど、時間を置いてもう一度解いてみようかな。

ソース

N, Q = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
L,R,V = [],[],[]
for _ in range(Q):
    l,r,v = [int(x) for x in input().split()]
    L.append(l-1)
    R.append(r-1)
    V.append(v)

# 左との差分(差分を更新していく)
D = [0] * N
for i in range(1, N):
    D[i] = A[i] - A[i-1]

# 現在のスコア(不便さ)
score = 0
for i in range(N-1):
    score += abs(A[i] - A[i+1])

# 各クエリの計算
for i in range(Q):
    # lからrがv増えるので、差分としては下記の2箇所が変更される
    # D[l] ・・・・[l-1]と[l]の差
    # D[r+1] ・・・[r]と[r+1]の差
    l,r,v = L[i], R[i], V[i]
    if l!=0:
        # 変更前の差分をのぞいて、変更後の差分を加える
        score -= abs(D[l])
        D[l] += v
        score += abs(D[l])
    if r+1<N:
        # 変更前の差分をのぞいて、変更後の差分を加える
        score -= abs(D[r+1])
        D[r+1] -=v
        score += abs(D[r+1])
    print(score)