[CSP-S 2024] 擂台游戏 题解

后天就 CSP2025 了我终于想起来订正 [CSP-S 2024] 擂台游戏 了。
谨以此篇，安慰去年考场上拼尽全力大战 \(2.5h\) 只获得 \(40pts\) 的自己。
思路来自于这篇题解。
约定

为了方便描述，我们做如下约定：

• 对于每个询问 \(c_i\)，我们把那些可以任意钦定能力值的编号 \(>c_i\) 的人称为 bot。对于编号 \(>n\) 的人他们始终是 bot，称为完全 bot。
  
• 把最终的二叉树画出来之后，对于一个点 \(u\)，我们设他的父亲是 \(fa_u\)，左儿子是 \(ls_u\)，右儿子是 \(rs_u\)，他管辖的区间为 \([L_u,R_u]\)，其子树内的获胜者为它的 winner，他的高度是 \(H_u\)（根的高度为 \(K\)，其中 \(K\) 是第一个满足 \(2^K\ge n\) 的数），换句话说他的两个儿子子树的 winner 在对决时擂主的能力值需要 \(\ge H_u\) 才能获胜。
  

观察

我们先做一些简单的观察：

• 如果子树内的全都是真人那么子树的 winner 是唯一的。
  
• 当某一次对决的擂主为 bot，我们可以任意钦定这次对决是谁赢。
  

证：如果要让 bot 赢，直接让他的能力值为 \(+\infty\) 即可；如果要让对手赢，注意到假设 bot 是 \(u\) 子树的 winner，他其实只需要满足 \(a_i \ge H_u\) 即可，因此我们直接令 \(H_u \to a_i\)，这样就有 \(a_i < H_{fa_u}=H_u+1\)，于是他就守擂失败了。

因此能感受到 bot 的可操作性很高，如果我们要让某一个人获胜，那么我们应该尽可能地给他安排 bot 作为对手，因为 bot 可以给他放水。
\(O(Tn^2m)\) + \(A\) 性质

考场上就只写出了这个。
根据结论 \(1\)，特殊性质 A 的单次询问答案是确定的，直接 DP 预处理即可。
对于 \(O(Tn^2m)\) 的做法，我们实现一个返回值为 vector 的函数 dfs(l,r) 表示当前询问下区间 \([l,r]\) 可能的 winner 的集合，假设 \([l,mid]\) 的 winner 的集合为 \(A\)，\([mid+1,r]\) 的集合为 \(B\)，擂主是 \([l,mid]\) 的 winner：

• 对于 \(A\) 中的点，只有它的能力值大于等于当前高度或者他是 bot 才可能赢。
  
• 对于 \(B\) 中的点，只要 \(A\) 中存在一个 bot 或者存在一个能力值小于当前高度的真人就能赢。
  

单次询问总共需要处理 \(O(n)\) 个这样的区间 \([l,r]\)，每次合并是 \(O(n)\) 的，因此总复杂度是 \(O(Tn^2m)\)。
加上 A 性质，期望得分 \(40pts\)。
下面是考场代码：
点击查看代码[code]#include#define int long long using namespace std;const int N=1e5+5;inline int read(){        int w=1,s=0;        char c=getchar();        for(;c'9';w*=(c=='-')?-1:1,c=getchar()) ;        for(;c>='0'&&c