JOI難易度６フェーン現象 - あっとのTECH LOG

問題原文

問題要旨

海から陸に向かって風が吹く。海から家までには $N$ 個地点があり、その標高は $A_i$ である。（ただし海も１つの地点として、 $A_0$ = 0 として与えられる）
温度0から始め、高度の変化に応じて温度が変化する。

$A_i ＜ A_{i + 1}$ のとき: 標高が１上がるごとに温度が $S$ 下がる
$A_i \geq A_{i + 1}$ のとき: 標高が１下がるごとに温度が $T$ 上がる

この条件のもと、以下のクエリを処理せよ。
- $L \leq K \leq R$ を満たす地点の標高を $X_q$ あげる。
- 現状での最後に届く温度はいくらかを出力

$1 \leq N, Q \leq 2×10^{5}$
$-10^{6} \leq A_i \leq 10^{6}$

解法

都度 $A_i$ を変更することも、 $A_i$ をなめることも制約上許されない。
少し観察すると、同時に標高が上がり下がりする範囲の山同士の「標高差」は変化しないことがわかる。
よって標高が上下することで影響があるのは、区間の両端と接している地点との標高だけである。
これは各 $q$ に対してたかだか２回までの再計算なので間にあう。

地点 $N$ の標高の変化は影響を与えないことに注意。

実装

出力時に正負を逆転させるようにすると楽。
下手に番兵をおくよりは $r$ の場合を分けて計算するとバグらせにくそう。
$X$ には「その地点の標高差で起きる温度の変化」が入っていて、これを使うことで「これまでの温度からその地点の温度の影響の排除」が楽にできる。

import sys
N, Q, S, T = map(int, input().split())
A = [int(sys.stdin.readline()) for _ in range(N + 1)]

# D > 0: S下がる, D <= 0: T上がる
# 出力時に正負逆転させることにする
D = [A[i] - A[i - 1] for i in range(1, N + 1)]
X = []
ans = 0
for d in D:
    if d > 0:
        ans += d * S
        X.append(d * S)
    else:
        ans += d * T
        X.append(d * T)

for q in range(Q):
    l, r, x = map(int, sys.stdin.readline().split())

    D[l - 1] += x
    ans -= X[l - 1]
    if D[l - 1] > 0:
        X[l - 1] = D[l - 1] * S
    else:
        X[l - 1] = D[l - 1] * T
    ans += X[l - 1]

    if r < N:
        D[r] -= x
        ans -= X[r]
        if D[r] > 0:
            X[r] = D[r] * S
        else:
            X[r] = D[r] * T
        ans += X[r]

    print(-ans)

感想

下手に番兵をおいてバグらせてしまった。