A85304 [CSP‑S2024]擂台游戏 精简题解
题意
每次询问给定 ccc，只看前 ccc 个选手。取最小 kkk 满足 2k≥c2^k\ge c2k≥c，补 2k−c2^k-c2k−c 个虚拟选手，总人数为 2k2^k2k。
共 kkk 轮比赛。第 RRR 轮第 GGG 场有抽签 dR,Gd_{R,G}dR,G ：
* (d=0)(d=0)(d=0)：编号小的为主擂；(d=1)(d=1)(d=1)：编号大的为主擂。
* 主擂获胜条件：自身能力值 ≥R\ge R≥R，对手能力无影响。
虚拟选手能力可以任意指定。只要存在赋值方案能拿到总冠军，该选手编号计入答案。
询问要输出所有可能夺冠选手的编号总和。
多组数据：aia_iai 由固定数组异或生成；抽签数组全局不变。虚拟选手也要计入答案。
核心结论
对真实选手 x≤cx\le cx≤c，要能夺冠，每一轮 RRR：
1. 若本场 xxx 是主擂：必须 ax≥Ra_x\ge Rax ≥R。
2. 若本场主擂是对手：
* 对手是虚拟选手：无约束。
* 对手是真实选手：必须该对手 aopp<Ra_{opp}<Raopp <R，否则对手必赢，xxx 无法夺冠。
> 虚拟选手一定可以夺冠，直接把 (c+1)∼2k(c+1) \sim 2^k(c+1)∼2k 的编号全部加到答案。
预处理
对所有编号 pospospos、所有可能的 kkk，预处理每一轮 RRR：
该轮比赛的主擂对手编号 (opp[pos][R])(opp[pos][R])(opp[pos][R])。只依赖抽签 ***，与测试数据无关。
算法流程
1. 读入数据，预处理 oppoppopp 表。
2. 每组测试数据生成 aaa 数组。
3. 本组询问离线，按 ccc 从小到大处理，维护合法真实选手的编号和。
4. 处理询问 ccc：
* 求 kkk，S=2kS=2^kS=2k。
* 答案 = 合法真实选手和 + (c+1)(c+1)(c+1) 到 SSS 的编号和。
5. 按原顺序输出答案。
易错点
1. 不要漏虚拟选手的编号和。
2. 获胜条件是 ≥R\ge R≥R，不是 (>R)(>R)(>R)。
3. 每个询问独立求 kkk，不一定用题目给出的全局最大 KKK。
4. 多组数据抽签数组不变，仅 aaa 数组变化。
最后看代码：
