NOI D2T2

Register_int · 2026-07-22 14:46:49 · 题解

考虑 Prufer 序列还原的过程。其实就是贪心地选择最小的能挂的来挂，那么节点序列应该是几乎递增的。设 j 表示上一个挂的节点的编号，i 为当前位置。

如果 a_{i-1} 是某种数的最后一次出现，且 a_{i-1}<j，说明这里挂的就是 a_{i-1}。
否则，不断增大 j 直到 j 在 a_{i\sim n-2} 没出现，将 j 挂上去。

我们称每个数最后出现的位置为 \text{endpos}，那么我们发现：连向 a_i 的节点其实就是最小的 j 满足：

j+\sum[k<j\land\text{endpos}_k<i]=i

对于查询 x_i,y_i，我们对 y_i 上挂的点二分找 x_i，x_i 上挂的点二分找 y_i 即可，可以用树套树上二分实现。问题转化为怎么维护区间的 \text{endpos}。这个是简单的。设区间长度为 len，那么 <len-1 的数的 \text{endpos} 可以扫描线扫掉，=len-1 的可以线段树二分现算。至此我们以 \mathcal{O}(n\log^2n) 的复杂度解决了此题。