题解：CF992E Nastya and King-Shamans
Trafford1894
·
·
题解
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 的贡献。线段树维护区间加、区间最大值即可。
CF 提交记录。