CF1584E Game with Stones 题解

Sol

考虑一个区间 \([l,r]\) 要如何才能合法。

显然 \(l\) 只能和 \(l+1\) 消耗，所以 \(a_{l+1}\ge a_l\)。

然后接着让 \(l+1\) 和 \(l+2\) 消耗，所以 \(a_{l+2}\ge a_{l+1}-a_l\)。

以此类推 \(a_{i}\ge a_{i-1}-a_{i-2}+a_{i-3}-\dots\)。移项得到 \(a_{i}+a_{i-2}+\dots- (a_{i - 1}+a_{i-3}+a_{i-5}+\dots)\ge 0\)。

注意到这个式子在 \(i \gets i+ 1\) 后，原来的数 \(s\) 会变成 \(a_i-s\)。

那么我们只需要维护每个以 \(i\) 为后缀的所有区间，然后删除和 \(<0\) 的区间并加上 \([i,i]\)，然后查询和为 \(0\) 的区间数量，可以用 map 实现。

注意 \(r-l+1\) 为偶数时，\(s_{l,r}=s_r-s_{l-1}\)，否则 \(s_{l,r}=s_r+s_{l-1}\)，其中 \(s_{i}\) 表示以 \(i\) 结尾且 \(i\) 符号为正的区间交替和。

Code

Link。