PKUWC2025 Day1 T2

来抛砖引玉一波。

先声明：我的做法基于维护的数据结构不同是 \(O(n\log^3{(n+m)}+m\log^2{(n+m)})\) 或者 \(O(n\sqrt{(n+m)}\log{n}+m\sqrt{(n+m)})\)。

我的思路大致就是：按照 \(x\) 从小到大处理所有询问。

记 \(p_i\) 为当前 \(i\) 号点的 \(x\) 级祖先。

然后考虑如何维护区间内的不同的 \(p_i\) 数目。一种方法是数颜色，另一种就是用 \(pre_i\) 表示所有和 \(i\) 相同深度的节点中，第 \(i\) 个位之前，上一个 \(p\) 的值等于 \(p_i\) 的位置出现在哪。

容易注意到，这个东西的变化量是小常数 \(O(n\log n)\) 级别的，证明就是 \(\text{DSU on Tree}\) 的过程——即每次合并的过程中最多只会修改两个 \(pre_i\) 的值。

然后我们的模型就转化成了：

• \(n\log n\) 次单点修改权值
• \(m\) 次区间查询小于特定值的数个数

这个东西就是一个动态二维数点，等价于静态三维数点。

可以用 \(\text{CDQ}\) 分治解决，或者用分块。

分块做法的话似乎是 LOJ6278 的弱化版