自动搬运

查看原文

来自洛谷，原作者为

	lsj2009 关关雎鸠，在河之洲

搬运于2025-08-24 23:05:34，当前版本为作者最后更新于2024-10-27 17:58:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

较为复杂，见原题。

Solution

闲话：

考场上实现出了本题的 $\mathcal{O}(T(n\log{n}+m))$ 的做法。

然后由于算错了复杂度瓶颈（我认为树的大小是 $\mathcal{O}(n\log{n})$ 的，是不是要滚回去复习噗叽组了？？？？），所以并没有尝试给出 $\mathcal{O}(T(n+m))$ 的做法。

赛后重新思考发现，其实这最后一步优化并不复杂（感觉远不如想出 $\mathcal{O}(n\log{n})$ 做法难）。

下面从考场上以及考后的思考过程给出本题的完整做法。

Part 1 $\mathcal{O}(Tmn\log{n})$ 做法

我们考虑拆贡献，变成判断每个 $i$ 能否成为 $n'=c_j$ 时最终的 winner；更一般的，我们先讨论 $n'=n$ 的做法。

那么我们此时会分两种情况（我们称一个不知道信息的选手为「自由选手」）：

1. $i\le n'$，也就是 $i$ 不是自由选手。
2. $i>n'$，也就是 $i$ 是自由选手。

我们考虑模拟 $i$ 不断打擂台打上去的过程：

1. 如果 在一个节点 $u$ 时 $i$ 作为擂主（令 $i$ 所在子树为 $v$），那么我们容易判断 $i$ 可不可以成为这一局的 winner，具体的：
   • 如果 $i$ 是自由选手直接跳过即可，因为我们令 $a_i\gets \infty$ 就可以解决所有问题。
   • 如果 $i$ 不是自由选手，那么我们判断 $a_i$ 和 $k$ 的大小关系即可；如果 $a_i<k$ 就直接 game over 了，$i$ 不可能成为最终的 winner。
2. 如果不是 $i$ 作为擂主，也就是 在 $v$ 的 brother 对局中的 winner 作为擂主，这个时候就很难办。
   • 如果 $v$ 的 brother 子树内 不存在自由选手，那我在该子树的 winner 是确定的，并且可以预处理出来，此时我们就看看这个人作为擂主能不能打过就好了。
   • 如果 $v$ 的 brother 子树内 存在自由选手，我们有结论是：
     • 不妨认为自由选手的力量值是 $\infty$，然后同样 把自由选手当作普通选手 同样进行预处理。
     • 如果最终自由选手是 $v$ brother 上的 winner，则我们直接判 $i$ 成为了 $u$ 的 winner。
     • 如果最终非自由选手是 $v$ brother 上的 winner，则我们判断该选手能否守擂成功即可；成功的话对于 $i$ 就 game over 了。

对于「结论」的说明：

我们不妨先考虑 不存在自由选手 的情况。

不过这个可能没有很清晰的定义，我们认为「不存在」的定义是：

• 如果一个非自由选手的对手是自由选手，则非自由选手自动获胜。

当然自由选手对战自由选手就爱咋地咋地，我们并不关心。

我们不妨先考虑在上面这条规则的情况下求出所有 winner。

则我们有结论是：根据真实规则下每个子树内的 winner 只有两种可能：

1. 在遵循上面规则情况下的 winner。
2. 一个自由选手。

证明是平凡的，大概而言就是说，你考虑设我原来的 winner 是 $k$，某个自由选手在某一轮成功干掉了 $k$，那么他在之后的轮次中 就可以复刻 $k$ 的事件，因为他的 $a$ 比 $k$ 强，对战的其他节点又是一样的，所以肯定可以成为最终的 winner。

好的，其实上面的说明有一个小问题：对战的其他节点有可能是不一样的！然而我们自下而上归纳，根据我们的结论，如果不一样则 说明他对战了另一个自由选手，那两个自由选手谁爱赢谁赢，这对于我们的初心——判断 $i$ 是否能成为最终的 winner 并没有影响。

好的，然后呢？

我们发现自由选手对 $i$ 有一个很强的优惠：自由选手可以随机应变！

具体的，其实我们发现让一个自由选手成为 $v$ brother 的 winner 我们并不要求他的 $a=\infty$，而仅仅只是 $a\ge k-1$ 就完全足够了；那么在这一轮对战中我们让 $a\gets k-1$，输掉这一轮对战，给 $i$ 让路即可！

这样子我们也就说明了我们上面的判断是没有任何问题的。

这样子我们对于单组询问就可以做到 $\mathcal{O}(n+n\log{n})$，分别为预处理和对于每个 $i$ 模拟向上跳的过程；总复杂度是 $\mathcal{O}(Tmn\log{n})$。

Part 2 $\mathcal{O}(T(n\log{n}+m))$ 做法

上面给出的做法我们需要对于每询问单独处理，太弱智了，考虑优化。

首先我们注意到其实不同的 $c_i$ 其实就是在对每个「极左」的子树内做这个游戏。

• 我们称一个节点 $u$ 是「极左」的，当且仅当从 $u$ 爬到根其一直作为左儿子。

那我们从 $i$ 往上爬时，没爬到一个极左的节点，我们就可能可以对一个范围（$c_j$ 得大于其左子树叶子节点个数，小于等于其本身叶子节点个数）内的 $c_j$ 产生贡献。

能不能把这些 $c_i$ 归到一起处理呢？？？

显然是可以的。我们注意到一个事情：

• 假若当 $n'=i$ 时自由选手可以成为 $u$ 的 winner，则当 $n'=i'(i'<i)$ 时则自由选手必然可以成为 $u$ 的 winner。

则我们考虑记录 $f_u,g_u$ 分别表示：正常做打擂台过程在 $u$ 处的 winner（根据 Part 1 所说，我们视本身就是自由选手（$i>n$）的 $a_i$ 视作 $\infty$）和如果想要让一个自由选手成为 $u$ 处的 winner，$n'$ 最大是多少（需要注意的是，这里的自由选手是针对 $n'$ 而言而不是 $n$）。

转移是简单的。具体可以看下面代码。

则我们每次从 $i$ 向上跳，维护一个 $\max{n'}$，跳到一个 $u$，如果 $i$ 作为擂主，$a_i<k$，就直接结束；否则判断 $a_{f_{v\text{'s brother}}}$ 是否大于等于 $k$，如果是则我们要将 $\max{n'}$ 向 $g_{v\text{'s brother}}$ 取 $\min$。

则最终 $i$ 到一个极左节点时，就会贡献固有的范围（注意作为非自由选手应该还要向 $[i,n]$ 取交，作为自由选手要向 $[1,i)$ 取交）和 $[1,\max{n'}]$ 的交集；注意到这是一个区间，差分计算即可。

单组数据预处理复杂度 $\mathcal{O}(n)$，计算答案复杂度 $\mathcal{O}(n\log{n}+m)$。

细节有点多，而且这个 Part 比较重要，下面给出代码，建议完全看懂后再阅读下一个 Part。

考场上可能大概写出来这么一坨史（这个是考后复刻，跟考场代码不完全一样，不过细节基本上一致）：

code link。

Part 3 $\mathcal{O}(T(n+m))$ 做法

这个做法还是很有前途的！

因为我们注意到一个非常牛的事情是：进行加法的区间个数只有 $\mathcal{O}(n)$ 个！

• 分析：因为作为极左节点，这样节点的子树深度恰好是 $[1,K]$ 各有一个！而一个深度为 $k$ 的极左节点会有 $\mathcal{O}(\text{叶子节点数量})=\mathcal{O}(2^k)$ 个区间贡献给他，而 $\mathcal{O}(\sum\limits_{i=1}^K 2^k)=\mathcal{O}(n)$。

所以区间数量是可以接受的！

甚至，更进一步的是，我们可以对这 $K$ 个子树全部进行一次遍历！

我们观察：一个节点 $i$ 向上爬要注意两点：

1. 会不会其作为擂主直接挂掉。
2. 他的对手作为擂主能不能守擂成功，如果可以要向他对手的 $g$ 取 $\min$。

我们发现其实 后面那个东西和 $a_i$ 根本没有任何关系！

而前者也是容易处理的。

具体的：我们考虑 从每一个极左节点开始自顶向下处理贡献。

我们考虑遍历时维护一个二元组 $(x,y)$，经过一条边 $u\to v$ 时，我们考虑模拟 $i$ 从 $v\to u$ 的过程：

1. 如果 $v$ 子树内的点到 $u$ 作为擂主，则将 $x$ 向当前的 $k$ 取 $\max$。
2. 如果 $v$ 子树内的点到 $u$ 不作为擂主，则判断 $v\text{'s brother}$ 能否守擂成功，如果可以则将 $y$ 向 $g_{v\text{'s brother}}$ 取 $\min$。

到达叶子节点时（也就是我们的 $i$），这时 $x$ 就可以判断 $i$ 在往上跳时能不能到达我们枚举的极左节点；而 $y$ 就可以描述贡献区间的额外约束。

根据上面的分析，这样子单次复杂度就是 $\mathcal{O}(n+m)$ 的！

常数有点小大，可能要精细实现/ng

有点细节，这里给出一份 AC 代码：

code link。

Part 4 另一种刻画方法——$\log$ 去哪了？

一些对于该题的额外思考。

我们考虑将这颗满二叉树刻画成线段树，那其实 $i$ 向上爬的过程中遇到的额外限制就好比是一个 tag，而其对答案的贡献就是一个 value，每次其实我们就是要实现一个东西 来支持 value 和 tag 的合并。

更细节的，我们在 Part 2 的代码中采取了 标记永久化 的写法。

然后我们带 $\log$ 的做法中比较蠢蛋的原因是，我们想要获知所有叶子节点的 value，然而我们发现 value 不支持合并！但是幸运的是 合并具有交换律，那么我们从每个叶子节点往上爬不断 $\operatorname{merge}(value,tag)$ 就好了。

这样子复杂度是带 $\log$ 的。

然而另外一种更好的方式是，我们不再采取 标记永久化，因为我们发现 tag 和 tag 也是可以合并的！我们直接自上而下把 tag 全部 push down 下去就好了。

这样子我们就仅仅只需要遍历整颗线段树，复杂度也就少一只 $\log$ 了。

如果还有其他看法（或者我有啥写错了），欢迎在评论区指出！