P11234 擂台游戏

lsj2009 · 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 的做法。

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

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

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

对于「结论」的说明：

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

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

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

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

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

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

在遵循上面规则情况下的 winner。

一个自由选手。

证明是平凡的，大概而言就是说，你考虑设我原来的 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 向上爬要注意两点：

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

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

而前者也是容易处理的。

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

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

如果 v 子树内的点到 u 作为擂主，则将 x 向当前的 k 取 \max。
如果 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 了。

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