题解

思路推导

题目要求一个长度为 $k+1$ 的窗口满足 $2^j a_{i+j}<2^{j+1}a_{i+j+1}$。约去公共因子 $2^j$ 后，每一项都等价于 $a_{i+j}<2a_{i+j+1}$。

因此，一个窗口合法，当且仅当它覆盖的连续 $k$ 对相邻元素全部满足上述不等式。问题转化为统计长度至少为 $k$ 的连续“好边”段所包含的长度为 $k$ 的小段数量。

做法

从左到右扫描所有相邻对。若当前相邻对满足 $a_i<2a_{i+1}$，令当前连续好边数加一；否则清零。每当连续好边数不小于 $k$，就有一个以当前位置结尾的新合法窗口，答案加一。

比较时使用 64 位整数计算 $2a_{i+1}$，避免 $a_{i+1}$ 接近 $10^9$ 时的边界问题。

正确性证明

由约分可知，窗口中的第 $j$ 个原不等式与相邻条件 $a_{i+j}<2a_{i+j+1}$ 等价，所以窗口合法恰好等价于其中连续 $k$ 条边全部为好边。

扫描到一条边时，维护量等于以该边结尾的最长连续好边段长度。若该长度至少为 $k$，则最后 $k$ 条好边唯一对应一个以当前位置结尾的合法窗口；若小于 $k$，则不存在这样的窗口。算法对每个可能的右端点恰计数一次，故得到全部且仅有合法窗口。

复杂度分析

每个元素只被扫描常数次，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。