P15850 [NOISG 2026 Finals] 宝石 / Gemstones 笔记

首先大家都知道配对的方法是用栈从左往右模拟，那么对于多次询问，我们可以给每个左端点都开一个栈，时间复杂度 $O(n^2)$。

但是 $n$ 个栈里很多信息都是重复的，比如 $a_{[5,8]}$ 可以消去，那么从 $a_3$ 开始的栈在栈底保留 $a_3,a_4$，后面的操作就会和 $a_5$ 开始的栈一致，关键在于如何共享栈状态，这启示用树状结构。

具体地，为了模拟栈的消除操作，我们采用字典树，从根节点（空串）出发不断插入 $a_i$，如果可以消除就往父节点走，否则就往下走创建新点。这样子对于可以消除的段，最终都会走回原点。

那么查询 $[l,r]$，就记录 $a_{l-1},a_r$ 在字典树上的位置，用 LCA 查询他们的树上距离即可。使用倍增 LCA，时间复杂度 $O(n\log n)$。