首先容易写出一个线性的 DP。设 $f_i$ 和 $g_i$ 分别表示当第 $i$ 枚硬币状态为正面朝上/反面朝上，且后面的硬币为初始状态时，开始第 $i \sim n - 1$ 次操作的最终结果。显然有 $f_i \geq g_i$，转移方程为：
- $f_n = a_n$，$g_n = 0$；
- 对于 $i$ 为奇数：$f_i = f_{i + 1} + a_i$，$g_i = \max(f_i, g_{i + 1} + a_i)$；
- 对于 $i$ 为偶数：$f_i = \min(f_{i + 1}, g_{i + 1} + a_i)$，$g_i = g_{i + 1}$。
考虑省去奇数处转移的 $a_i$，最后额外加上，那么转移变为 $f_i = f_{i + 1}$，$g_i = \max(f_i - a_i, g_{i + 1})$。
观察到此时转移有如下性质：$f_i - g_i = \min(\{a_i, a_{i + 1}, \cdots, a_n\})$。当 $i$ 为后缀最小值时，若 $i$ 为奇数则调整 $g$ 值，否则调整 $f$ 值。
最终要求 $f_1$。那么只需要维护所有奇数位置的 $a_i$ 的和，以及所有偶数处的后缀最小值的贡献（贡献等于相比上一个后缀最小值的变化量）。用一个 std::set 维护所有后缀最小值的位置，由于修改只会变小，所以修改一个位置时，只可能删除一段后缀最小值，或者加上自己作为后缀最小值。
总时间复杂度为 $\mathcal{O}((n + q) \log n)$。