LG6779 [Ynoi2009] rla1rmdq

发布于 2021-07-26  1.02k 次阅读


题目链接

题意

给定一棵 $n$ 个点的有边权有根树,和一个长为 $n$ 的序列 $a$。接着有 $m$ 个操作:

  1. 给定 $l,~r$,将区间 $[l,~r]$ 中的每一个元素变为它在树上的上一级结点编号。
  2. 给定 $l,~r$,问区间内 $[l,~r]$ 内与根节点距离最近的结点到根节点的距离。

$n,~m \le 2 \times 10^5$,边权为非负整数

分析

考虑以 $\sqrt n$ 大小分块,对每一块维护块内答案。

容易发现当只有整块操作时,如果在某一时刻某个块内元素 $A$ 到达了块内另一元素 $B$ 在该时刻前已到达过的位置,在接下来的操作中 $A$ 将不再会对该块块内答案产生贡献,因为接下来的每一时刻 $B$ 都一定为 $A$ 的祖先,其到根节点距离一定小于 $A$ 到根节点距离。因此我们可以考虑在遇到这样的情况时将 $A$ 从块中删除,不再在之后的操作中更新 $A$,显然不会对答案产生影响,这样的话块内所有节点在树上对应最多只会覆盖整棵树 $O(n)$ 个结点,即块内时间复杂度为 $O(n)$,总时间复杂度为 $O(n \sqrt n)$。

在修改区间的边缘所在块时,我们可以考虑直接暴力重算修改部分。虽然这可能导致部分已删除的点被重新加入块内,但是并不影响块内总体时间复杂度。需要暴力将块内结点向上跳时可以使用重链剖分维护,在同一重链中跳跃的时间复杂度为 $O(1)$,每个点经过轻边的次数不超过 $O(\log n)$,因此全局花在暴力上移结点的总时间复杂度为 $O(n \log n)$。

总时间复杂度 $O((n+m) \sqrt n)$,比较考验卡常水平,可以参考代码中的卡常方法。

代码

View On Github


我缓慢吐出一串啊吧啊吧并不再想说话