# 小Y的线段树：前驱链与倍增

[alternative-binary-lifting.cpp](alternative-binary-lifting.cpp) 先处理序列，随后每读一个询问就给出答案，不需要保存全部询问。它覆盖完整数据范围。

## 从右往左看最终栈

区间的最后一个位置 $r$ 一定留在栈顶。它下面的元素，是 $r$ 左侧最近一个值严格大于 $a_r$ 的位置；其余更靠右的元素均会被 $a_r$ 弹出。继续往左应用同一规则，得到整条栈。

令 $p(i)$ 为 $i$ 左侧最近且满足 $a_{p(i)}>a_i$ 的位置，不存在时为零。用严格递减的单调栈可在线性时间求出全部 $p$ ：处理 $a_i$ 前弹出所有不大于它的值，此时栈顶即为 $p(i)$ .

于是 $[l,r]$ 的最终栈从顶到底依次为 $r,p(r),p(p(r)),\ldots$ ，直到下一位置小于 $l$ .所有前驱均严格向左，链不含环。相等元素不会成为前驱。

## 用倍增计数

预处理 $J_0(i)=p(i)$ ，$J_k(i)=J_{k-1}(J_{k-1}(i))$ ，并令 $J_k(0)=0$ .$J_k(i)$ 是跳过 $2^k$ 条前驱边后的节点。

对询问从 $r$ 开始，答案初始为一。从最大 $k$ 向下检查：若 $J_k(r)\ge l$ ，就跳到该节点，答案增加 $2^k$ .链上的编号严格减小，因此终点仍在区间时，中途经过的每个节点也在区间。按二进制贪心取跳步，最终恰好计入所有位于区间内的链节点，故答案正确。

设倍增层数为 $\lfloor\log_2N\rfloor+1$ .预处理 $O(N\log N)$ ，每次询问 $O(\log N)$ ，总空间 $O(N\log N)$ ，无需 $O(M)$ 的询问存储。与[首选解法](solution.zh.md)相比，它用更多预处理和存储换取逐条回答的组织方式。GPT-6 应用经典前驱链与倍增补充该方案，并提供证明与实现；小规模逐询问模拟以及正式数据核对均通过。实测见[性能记录](../../../docs/benchmark-R25.json)。