题解：CF992E Nastya and King-Shamans

NOIp 前写题解，RP ++。

注意到 $a_i=s_{i-1}$ 是一个较难满足的条件，可以想到合法 $a_i$ 的数量一定不多。具体地，如果 $a_i = s_{i-1}$，则 $s_i = 2 \times s_{i-1}$。则合法的 $i$ 只有 $O(\log n)$ 个。

考虑对于每一个 $i$，维护 $a_i-s_{i-1}$ 的区间最大值。在查询的时候如果最大值 $\geq 0$ 则可能有解。因为合法 $i$ 的数量只有 $O(\log n)$ 个，直接判断即可。

单点修改时会对 $i$ 产生 $a_i - x$ 的贡献，对于 $[i+1,n]$ 会产生 $x - a_i$ 的贡献。线段树维护区间加、区间最大值即可。