题解：P15850 [NOISG 2026 Finals] 宝石 / Gemstones

· · 题解

:::info[前言]

为什么有超过一半的同学使用莫队过的？

:::

题意：给定一个序列，多次询问，支持查询某一个区间按某种顺序消除相邻两个数后所能剩下的数最少是多少。

看到这种题，如果没有思路的话，可以看一下部分分。

注意到对于 Subtask 4 的每一个 l_j 都为 1 这个特殊性质好像很有启发意义，让我们思考一下。

发现对于这个 Subtask 只需要用栈模拟一遍前缀就可以了，这给了我们启发，答案是不是可以用前缀表示。

考虑一下这个过程，对于每一个 i，如果栈顶与 i 的颜色相同，那就把栈顶弹出，否则把这个 i 加入。

这个操作可以抽象为一棵树：弹出等于往父亲走，加入等于往儿子走。初始为空栈，我们用一个虚拟根 0 表示，深度为 0。每处理一个数后，我们在树上走到一个节点，用 pos_i 表示处理完前 i 个数后所在的节点，那么 dep_{pos_i} 就是当前栈的大小（也就是剩下多少个宝石）。

那么我们就可以建树了，树边就表示对栈的操作，深度就表示当前栈的大小。

对于一个询问 [l,r]，我们是从状态 pos_{l-1} 开始，把区间里的数依次处理，最后会停在 pos_r。由于无论以什么顺序消除相邻相同对，最终剩下的序列是唯一的（就是栈模拟的结果），所以答案就是最终剩下的宝石数。

再手模几个，发现答案就是 pos_{l-1} 和 pos_r 在树上对应的点之间的距离，也就是 dep_{pos_{l-1}}+dep_{pos_r}-2\times dep_{\mathrm{LCA}(pos_{l-1},pos_r)}。

感性证明一下，这两个点的 LCA 表示的就是它们栈的公共底部部分——这些宝石在 l-1 时就已经在栈里，而且经过 [l,r] 的操作后依然没被消掉，所以它们对区间操作来说是无关的。真正被区间影响到的部分，就是 pos_{l-1} 到 LCA 的一段（被区间操作消掉了），以及 LCA 到 pos_r 的一段（区间里新压入且未被消掉的），这两段长度加起来就是剩下的宝石数。

于是乎建树就做完了。

复杂度 \mathcal{O}(n\log n+q\log n)，瓶颈在于求 LCA。（当然也可以用欧拉序+ST 表做到 \mathcal{O}(n\log n+q)。）