@[tratser](/user/709949) 看上去每次倍增（`while (len)` 循环）是 $O(\log n)$ 的，整体是 $O(n)$ 的
Proof: 记某次倍增**之后**的 len 值为 $l$。一开始 len 从 $0$ 开始上升，每次乘上 $2$，所以是 $\Theta(\log l)$ 的。
在此之后 len 的值只有当 `if` 里面的条件为真时才上升，而每次满足 `if` 时的 $l$ 值一定是单调递减的，所以也是 $\Theta(\log l)$.
合起来就是 $\Theta(\log l)=O(\log n)$.
by esquigybcu @ 2022-07-20 14:06:44
@[pzq_loves_qwq](/user/384214) 感谢，那请问为什么整体是 $O(n)$ 的呢？
by M1rac0 @ 2022-07-20 14:28:57
@[tratser](/user/709949) 因为每次倍增是 $\Theta(\log l)$ 的，但是往后走了 $l$ 个元素，所以每个元素均摊是 $O(1)$ 的
by esquigybcu @ 2022-07-20 14:34:29
@[pzq_loves_qwq](/user/384214) 所以总复杂度不应该是 $O(\log n)$ 吗 /kel
by M1rac0 @ 2022-07-20 15:31:00
@[tratser](/user/709949) 好像也不对……
by M1rac0 @ 2022-07-20 20:57:51
@[tratser](/user/709949) 考虑一个除了一个元素都 $\ge m$ 的序列
by esquigybcu @ 2022-07-21 10:06:57
@[pzq_loves_qwq](/user/384214) 确实，所以我感觉复杂度大概是 $O(\sum \dfrac{(r-l)}{\log{(r-l})})$，即最好情况下 $O(\log n)$，最坏情况下 $O(n)$ 的
by M1rac0 @ 2022-07-21 11:58:26
@[tratser](/user/709949) 对，所以是 $O(n)$ 的，没问题
by esquigybcu @ 2022-07-21 12:03:31
@[pzq_loves_qwq](/user/384214) 明白了 /se /se /se /se
by M1rac0 @ 2022-07-21 13:59:43