来自自己的木棉题解

Iniaugoty · 2026-07-22 18:02:16 · 题解

最后的维护使用整体二分，没有树套树。

我本来想说这个做法完全没有细节，但是考虑到我自己考场上都没有调出来，所以我决定换个说法：这个做法想清楚了再写完全没有细节，但你要先想好了，我考场上本质没有想明白，哈哈哈。

先把区间当成 n 个点的全局来研究，并在最后添加一个 n 来减少讨论。

我们考虑如何求出构建 prufer 序列的过程中 x 被删除的时间，这样直接能知道 x 的父亲是谁，对 x, y 分别跑一遍可以知道答案（可以只跑一遍，但是正常人类的思维路径这里应该还想不到这一点）。

回顾线性求 prufer 序列的过程：维护指针 p 初始为 1，若 p 是叶子就删除，然后不断进行“如果父亲变成了叶子并且比 p 小就删除”，最后 p \gets p + 1。这个过程中，x 被删除时一定是一条链 y \rightsquigarrow x \rightsquigarrow z，从 y 到 z 依次被删除，且其中 y 是链上最大的点；这个链最后被删除，在此之前被删除的所有点都 < y。

这里先提一个后面有用的观察是：在一个后缀中没有出现的数，意味着他在前面已经被删除，或者在当前时刻是叶子。记 C(a,b) 表示下标 [a,n-1] 中没有出现过的值域 [1,b) 的数的个数。

设 y 被删除的时刻是 t_y，根据上面的分析和观察，一个显然的必要条件是 C(t_y, y) = t_y-1 且 y 最后一次出现在 t_y 以前。分析等式两边的增量，可以发现满足这个条件的 t_y 是一段区间，每个时刻上的数都是自己的最后一次出现。x 在这个区间中的存在性有两种情况：

• 出现过 x：则 t_y \le x 出现的时刻，并且从 t_y 开始一直到 x 出现这之间的一段数就是从 y 的父亲到 x 的链，则 t_x 为 x 出现后的下一个时刻。同时 C(t_x,x) - C(t_y,y) = t_x - t_y。

• 没有出现过 x：t_x 只能是区间的左端点，并且这时 x=y，因为如果 x 在后面的任何时刻被删除，都会在上一个时刻出现在序列里。

因此我们发现对于 y 的必要条件对 x 也是必要的，并且由于得到的结果唯一其也是充分的。

问题转化成：求最小的 t 使得 [t,n-1] 中没有出现过 x，且 t-1 \ge C(t,x)。二分 t，之后要做一个三维偏序，里面直接树套树是 O(\log^3 n) 的。

离线整体二分，对于所有询问区间 [ql,qr] 与当前序列区间 [l,r] 有交的询问，判断区间中点是否合法，需要算右侧的一段前缀，先把未出现改写成总数减去出现，接下来略麻烦，如果 qr \le r 就用第一次出现的位置 \le qr 来刻画出现过；否则把 (r,qr] 部分出现过的先算上（在递归前几层必然算过），然后用 r 以后第一次出现位置 >qr 来刻画新的数的出现。对值域扫描线来刻画 [1,x)，两种情况分别树状数组维护是简单的。

时间复杂度 O(n \log^2 n)，空间复杂度 O(n)。

https://qoj.ac/submission/2669543