擂台游戏
题目描述:
小 S 想要举办一场擂台游戏，如果共有 \(2^k\) 名选手参加，那么游戏分为 \(k\) 轮进行：
- 第一轮编号为 \(1, 2\) 的选手进行一次对局，编号为 \(3, 4\) 的选手进行一次对局，以此类推，编号为 \(2^k - 1, 2^k\) 的选手进行一次对局。
- 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
- 以此类推，第 \(k - 1\) 轮在只保留第 \(k - 2\) 轮的 \(4\) 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
- 第 \(k\) 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 \(a_1, a_2, \dots , a_{2^k}\)，能力值为 \([0,2^{31}-1]\) 之内的整数。对于每场比赛，会先抽签决定一个数 \(0/1\)，我们将第 \(R\) 轮的第 \(G\) 场比赛抽到的数记为 \(d_{R,G}\)。抽到 \(0\) 则表示表示编号小的选手为擂主，抽到 \(1\) 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 \(a\geq R\)。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。
现在，小 S 先后陆续收到了 \(n\) 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 \(1, 2, \dots, n\)。小 S 关心的是，补充尽量少的选手使总人数为 \(2\) 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的**编号之和**是多少。
形式化地，设 \(k\) 是最小的非负整数使得 \(2^k\geq n\)，那么应当补充 \((2^k-n)\) 名选手，且补充的选手的能力值可以任取 \([0,2^{31}-1]\) 之内的整数。如果补充的选手有可能取胜，也应当计入答案中。
当然小 S 觉得这个问题还是太简单了，所以他给了你 \(m\) 个询问 \(c_1,c_2,\dots,c_m\)。小 S 希望你帮忙对于每个 \(c_i\) 求出，在只收到前 \(c_i\) 位选手的报名信息时，这个问题的答案是多少。
输入格式:
共输出 \(T\) 行，对于每组数据，设 \(A_i\) 为第 \(i\)（\(1 \leq i \leq m\)）组询问的答案，你只需要输出一行包含一个整数，表示 \((1\times A_1) \oplus (2\times A_2) \oplus \dots \oplus (m\times A_m)\) 的结果。
样例输入:
样例1 5 5 0 0 0 0 0 5 4 1 2 3 1001 10 1 4 2 1 0 0 1 2 1 0 0 2 3 1 2 2 0 1
样例输出:
样例1 5 19 7 1
提示:
【样例 1 解释】
共有 \(T = 4\) 组数据，这里只解释第一组。\(5\) 名选手的真实能力值为 \([1, 0, 0, 2, 1]\)。\(5\) 组询问分别是对长度为 \(5, 4, 1, 2, 3\) 的前缀进行的。
1. 对于长度为 \(1\) 的前缀，由于只有 \(1\) 号一个人，因此答案为 \(1\)。
2. 对于长度为 \(2\) 的前缀，由于 \(2\) 个人已经是 \(2\) 的幂次，因此不需要进行扩充。根据抽签 \(d_{1,1} = 1\) 可知 \(2\) 号为擂主，由于 \(a_2 < 1\)，因此 \(1\) 号获胜，答案为 \(1\)。
3. 对于长度为 \(3\) 的前缀，首先 \(1\) 号、\(2\) 号比赛是 \(1\) 号获胜（因为 \(d_{1,1} = 1\)，故 \(2\) 号为擂主，\(a_2 < 1\)），然后虽然 \(4\) 号能力值还不知道，但 \(3\) 号、\(4\) 号比赛一定是 \(4\) 号获胜（因为 \(d_{1,2} = 0\)，故 \(3\) 号为擂主，\(a_3 < 1\)），而决赛 \(1\) 号、\(4\) 号谁获胜都有可能（因为 \(d_{2,1} = 1\)，故 \(4\) 号为擂主，如果 \(a_4 < 2\) 则 \(1\) 号获胜，\(a_4 \geq 2\) 则 \(4\) 号获胜）。综上所述，答案为 \(1 + 4 = 5\)。
4. 对于长度为 \(4\) 的前缀，我们根据上一条的分析得知，由于 \(a_4 \geq 2\) ，所以决赛获胜的是 \(4\) 号。
5. 对于长度为 \(5\) 的前缀，可以证明，可能获胜的选手包括 \(4\) 号、\(7\) 号、\(8\) 号，答案为 \(19\)。
因此，该组测试数据的答案为 \((1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 5) = 5\)。
【样例 2】
见选手目录下的 arena/arena2.in 与 arena/arena2.ans。
这组样例满足特殊性质 A。
【样例 3】
见选手目录下的 arena/arena3.in 与 arena/arena3.ans。
这组样例满足特殊性质 B。
【样例 4】
见选手目录下的 arena/arena4.in 与 arena/arena4.ans。
【样例 5】
见选手目录下的 arena/arena5.in 与 arena/arena5.ans。
【数据范围】
对于所有测试数据，保证：\(2 \leq n, m \leq 10^5\)，\(0 \leq a_i, X_j < 2^{31}\)，\(1 \leq c_i \leq n\)，\(1 \leq T \leq 256\)。
| 测试点 | \(T=\) | \(n,m\leq\) | 特殊性质 A | 特殊性质 B |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| \(1\sim 3\) | \(1\) | \(8\) | 否 | 否 |
| \(4,5\) | \(1\) | \(500\) | 是 | 否 |
| \(6\sim 8\) | \(1\) | \(500\) | 否 | 是 |
| \(9,10\) | \(1\) | \(5000\) | 否 | 否 |
| \(11,12\) | \(1\) | \(10^5\) | 是 | 否 |
| \(13\sim 15\) | \(1\) | \(10^5\) | 否 | 是 |
| \(16,17\) | \(4\) | \(10^5\) | 否 | 否 |
| \(18,19\) | \(16\) | \(10^5\) | 否 | 否 |
| \(20,21\) | \(64\) | \(10^5\) | 否 | 否 |
| \(22,23\) | \(128\) | \(10^5\) | 否 | 否 |
| \(24,25\) | \(256\) | \(10^5\) | 否 | 否 |
特殊性质 A：保证询问的 \(c_i\) 均为 \(2\) 的幂次。
特殊性质 B：保证所有的 \(d_{R,G} = 0\)。
时间限制: 1000ms空间限制: 512MB
来源: CSP2024提高T4