3703. T4-[CSP-S 2024] 擂台游戏duel
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 小 $ S $ 想要举办一场擂台游戏，如果共有 $ 2^k $ 名选手参加，那么游戏分为 $ k $ 轮进行： - 第一轮编号为 $ 1,2 $ 的选手进行一次对局，编号为 $ 3,4 $ 的选手进行一次对局，以此类推，编号为 $ 2^k-1,2^k $ 的选手进行一次对局。 - 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。 - 以此类推，第 $ k-1 $ 轮在只保留第 $ k-2 $ 轮的 $ 4 $ 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。 - 第 $ k $ 轮即为半决赛两位胜者的决赛。 确定了游戏晋级的规则后，小 $ S $ 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 $ a_1,a_2,···,a_{2^k} $ ，能力值为 $ [0,2^{31}-1] $ 之内的整数。对于每场比赛，会先抽签决定一个数 $ 0/1 $ ，我们将第 $ R $ 轮的第 $ G $ 场比赛抽到的数记为 $ d_{R,G} $ 。抽到 $ 0 $ 则表示表示编号小的选手为擂主，抽到 $ 1 $ 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 $ a\geR $ 。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。 现在，小 $ S $ 先后陆续收到了 $ n $ 位选手的报名信息，他们分别告知了小 $ S $ 自己的能力值。小 $ S $ 会按照报名的先后顺序对选手进行编号为 $ 1,2,···,n $ 。小 $ S $ 关心的是，补充尽量少的选手使总人数为 $ 2 $ 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和为多少。 形式化地，设 $ k $ 是最小的非负整数使得 $ 2^k\gen $ ，那么应当补充 $ (2^k-n) $ 名选手，且补充的选手的能力值可以任取 $ [0,2^{31}-1] $ 之内的整数。如果补充的选手有可能获胜，也应当计入答案中。 当然小 $ S $ 觉得这个问题还是太简单了，所以他给了你 $ m $ 个询问 $ c_1,c_2,···,c_m $ 。小 $ S $ 希望你帮忙对于每个 $ c_i $ 求出，在只收到前 $ c_i $ 位选手的报名信息时，这个问题的答案是多少。 ## 输入格式 从文件 $ arenain $ 中读入数据。 本题的测试点包含有多组测试数据，但不同测试数据只是通过修改 $ a_1,a_2,···,a_n $ 得到，其他内容均保持不变，请参考以下格式。其中⊕代表异或运算符， $ a\ mod\ b $ 代表 $ a $ 除以 $ b $ 的余数。 输入的第一行包含两个正整数 $ n,m $ ，表示报名的选手数量和询问的数量。 输入的第二行包含 $ n $ 个非负整数 $ a'_1,a'_2,···,a'_n $ ，这列数将用来计算真正的能力值。 输入的第三行包含 $ m $ 个正整数 $ c_1,c_2,···,c_m $ ，表示询问。 设 $ K $ 是使得 $ 2^K\gen $ 的最小的非负整数，接下来的 $ K $ 行当中，第 $ R $ 行包含 $ 2^{K-R} $ 个数（无空格），其中第 $ G $ 个数表示第 $ R $ 轮的第 $ G $ 场比赛抽签得到的 $ d_{R,G}=0/1 $ 。 注意，由于询问只是将人数凑齐到 $ 2^k\gec_i $ ，这里的 $ k\leK $ ，因此你未必会用到全部的输入值。 接下来一行包含一个正整数 $ T $ ，表示有 $ T $ 组测试数据。 接下来共 $ T $ 行，每行描述一组数据，包含 $ 4 $ 个非负整数 $ X_0,X_1,X_2,X_3 $ ，该组数据的能力值 $ a_i=a'_i⊕X_{i\ mod\ 4} $ ，其中 $ 1\lei\len $ 。 ## 输出格式 输出到文件 $ arena.out $ 中。 共输出 $ T $ 行，对于每组数据，设 $ A_i $ 为第 $ i（1 \le i \le m） $ 组询问的答案，你只需要输出一行包含一个整数，表示 $ (1 \times A_1) ⊕ (2 \times A_2) ⊕ · · · ⊕ (m \times A_m) $ 的结果。 ## 输入 ```in1 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 ``` ## 输出 ```out1 5 19 7 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\ge2 $ 则 $ 4 $ 号获胜）。综上所述，答案为 $ 1+4=5 $ 。 4. 对于长度为 $ 4 $ 的前缀，我们根据上一条的分析得知，由于 $ a_4\ge2 $ ，所以决赛获胜的是 $ 4 $ 号。 5. 对于长度为 $ 5 $ 的前缀，可以证明，可能获胜的选手包括 $ 4 $ 号、 $ 7 $ 号、 $ 8 $ 号，答案为 $ 19 $ 。 因此，该组测试数据的答案为 $ (1\times19)⊕(2\times4)⊕(3\times1)⊕(4\times1)⊕(5\times5)=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 \le n, m \le 10^5，0 \le a_i , X_j < 2^{31}，1 \le c_i \le n，1 \le T \le 256 $ 。 特殊性质 $ A $ ：保证询问的 $ c_i $ 均为 $ 2 $ 的幂次。 特殊性质 $ B $ ：保证所有的 $ d_{R,G}= 0 $ 。