Description

Link：CF992E

Solution

注意到 $a_i \geq 0$。若 $a_i = s_{i - 1}$，则 $s_i = 2s_{i - 1}$。故满足要求的位置个数是 $\mathcal{O}(\log a)$ 级别的。

进一步，考虑 $a_i \geq s_{i - 1}$ 即 $s_i \geq 2s_{i - 1}$。满足该要求的位置个数也是 $\mathcal{O}(\log a)$ 级别的。

使用线段树维护 $a_i - s_{i - 1}$ 的最大值。每次暴力地遍历整棵线段树，遇到最大值 $< 0$ 的区间就返回，遇到一个叶子就判断该点对应的 $a_i - s_{i - 1}$ 是否等于 $0$。

时间复杂度 $\mathcal{O}(n \log n \log a)$。