概要
たぶん最終的なアルゴリズムは一緒ですが、思考過程は割と違いそうなので、書いてみます。愚直解法を作ってから、漸化式を観察することで高速な解法を探ります。
$O(NQ)$ 解法（クエリごとの $O(N)$ 解法）
ゲームの最善手に関する考察は、決着間際から遡るのが原則だと思います。例えば、残り 1 手という状況であれば最善手は簡単に決定できます。
マス $n$ 以降でゲームをするときの、先手（マス $n$ に石を置く人）のスコアから後手のスコアを引いた値の最大値を、次のように $\dp[n]$ とします。
- マス $n$ の表裏が（直前の手番の人によって）操作されていない場合：$\dp_0[n]$
- マス $n$ の表裏が（直前の手番の人によって）操作されている場合：$\dp_1[n]$
すると次の解法になると思います（https://atcoder.jp/contests/dwango2015-honsen/submissions/20201131）。
N = len(A)
Asum = A.sum()
dp_0 = np.zeros(N, np.int64)
dp_1 = np.zeros(N, np.int64)
dp_0[N - 1] = A[N - 1]
dp_1[N - 1] = -A[N - 1]
for i in range(N - 2, -1, -1):
x = A[i]
dp_0[i] = max(-x - dp_0[i + 1], +x - dp_1[i + 1])
dp_1[i] = max(+x - dp_0[i + 1], -x - dp_1[i + 1])
print((Asum + dp_0[0]) // 2)添字を逆順に回すのが面倒に感じたので、配列 $A$ を逆順にしておきます（https://atcoder.jp/contests/dwango2015-honsen/submissions/20201193）。
A = A[::-1]
N = len(A)
Asum = A.sum()
dp_0 = np.zeros(N, np.int64)
dp_1 = np.zeros(N, np.int64)
dp_0[0] = A[0]
dp_1[0] = -A[0]
for i in range(1, N):
x = A[i]
dp_0[i] = max(-x - dp_0[i - 1], +x - dp_1[i - 1])
dp_1[i] = max(+x - dp_0[i - 1], -x - dp_1[i - 1])
print((Asum + dp_0[-1]) // 2)式変形
ここから先は、問題の設定に戻っても仕方がないと思ったので、上のコードの漸化式を観察することで、良い性質を探します。特に、$\max$ のどちらが採用されるかが決まらないのが難点です。
とりあえず愚直解法を作ったので、ランダムケースを大量に観察して適当な予想を立てたり検証したりできるようになりました。その結果、ひとつめの式：$\dp_0[i] = \max\{-x – \dp_0[i – 1], +x – \dp_1[i – 1]\}$ では常に後者が採用されることを発見します。
証明は簡単で、$\dp_0[i]\geq \dp_1[i]$ を帰納法で示すことが可能です。$x\geq 0$ を使いますね。
$\dp_0[i-1]\geq \dp_1[i-1]$ を仮定すると、$\dp_0[i] = x – \dp_1[i-1]$ が分かり、帰納法の仮定から $x – \dp_1[i-1] \geq x – \dp_[i-1]$、$x\geq 0$ から $x – \dp_1[i-1]\geq -x – \dp_1[i-1]$ が分かるので、$\dp_0[i] \geq \dp_1[i-1]$ が従います（https://atcoder.jp/contests/dwango2015-honsen/submissions/20201525）。
dp_0[0] = A[0]
dp_1[0] = -A[0]
for i in range(1, N):
x = A[i]
dp_0[i] = +x - dp_1[i - 1]
dp_1[i] = max(+x - dp_0[i - 1], -x - dp_1[i - 1])
print((Asum + dp_0[-1]) // 2)もうひとつの $\max$ はよく分かりません。しかし、$\dp_0[i]$ と $\dp_1[i]$ の差だ重要だということは読み取れます。さらに、$\dp_0[i] – \dp_1[i]$ の値が $\dp_0[i-1] – \dp_1[i-1]$ だけから定まることが観察できます（$\dp_0[i-1], \dp_1[i-1]$ の値がともに $k$ 増加したら、$\dp_0[i]$, $\dp_1[i]$ はともに $k$ 減少する）。
そこで新たに $\dp_2[i] := \dp_0[i] – \dp_1[i]$ とおきましょう。$(\dp_0, \dp_1)$ から $(\dp_0, \dp_2)$ へと変数変換します。
$\dp_0[i] = x – \dp_1[i-1]$ より $\dp_0[i] = x – (\dp_0[i-1] – \dp_2[i-1]) = -\dp_0[i-1] + x + \dp_2[i-1]$ が得られ、
$\dp_0[i] – \dp_1[i] = \min\{\dp_0[i-1]- x-\dp_0[i-1], 2x\}$ より $\dp_2[i] = \min\{\dp_2[i-1], 2x\}$ が得られます（https://atcoder.jp/contests/dwango2015-honsen/submissions/20437024）
dp_0[0] = A[0]
dp_2[0] = 2 * A[0]
for i in range(1, N):
x = A[i]
dp_0[i] = -dp_0[i - 1] + x + dp_2[i - 1]
dp_2[i] = min(dp_2[i - 1], 2 * x)
print((Asum + dp_0[-1]) // 2)これは、やはり $2$ 数列からなる漸化式ですが、
- まず、全ての $\dp_2$ が計算できる
- 次に、それを踏まえて $\dp_0$ が全て計算できる
という仕組みになっていて、$1$ つの数列に関する漸化式 $2$ 回に分離されています。
特に、$\dp_2$ の値は簡単です。$\dp_2[i] = 2 * \min\{A[0], A[1], \ldots, A[i]\}$ となります。
次に、$\dp_0$ の計算規則を確認していきます。高校数学っぽく書くなら、漸化式 $a_i = -a_{i-1} + f(i-1)$ の形の漸化式を解きましょうという話です。これは、$b_i = (-1)^ia_i$ の形の変数変換が高校数学でもテンプレですね。
そこで、$\dp_3[i] := (-1)^i\dp_0[i]$ と変数変換します。
dp_2 = np.zeros(N, np.int64)
dp_2[0] = 2 * A[0]
for i in range(1, N):
dp_2[i] = min(dp_2[i - 1], 2 * A[i])
dp_3 = np.zeros(N, np.int64)
dp_3[0] = A[0]
for i in range(1, N):
x = A[i]
sgn = (-1) ** i
dp_3[i] = dp_3[i - 1] + sgn * x + sgn * dp_2[i - 1]
sgn = (-1) ** (N - 1)
print((Asum + sgn * dp_3[-1]) // 2)だいぶ分かりやすくなってきました。$\dp_3$ は何かの累積和をとっているだけです。それの最終項だけを答の出力に使うため、答は数列の和として記述できます。
dp_2 = np.zeros(N, np.int64)
dp_2[0] = 2 * A[0]
for i in range(1, N):
dp_2[i] = min(dp_2[i - 1], 2 * A[i])
x = A[0]
for i in range(1, N):
x += (-1) ** i * A[i]
x += (-1) ** i * dp_2[i - 1]
sgn = (-1) ** (N - 1)
print((Asum + sgn * x) // 2)クエリ処理
ここまで出来ればあとは（本問挑戦適正レベルであればたぶん）簡単です。
クエリ間で、各 $A[i]$ の寄与 $(-1)^iA[i]$ の差分を求めることは簡単にできます。
$\dp_2$ については、変更クエリが $A[i]$ を下げる方向にしか行われないという設定が重要です。変更後の $\dp_2$ は変更前の $\dp_1$ だけから計算できます（$i$ 番目以降で、$A[i]$ との $\min$ をとる）。 $\dp_2$ が定数である区間をまとめて管理すれば、償却 $O(N+Q)$ 回の区間の挿入・削除で済みます。
