2220: 擂台游戏

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：2 Solved：0

Description

小 S 想要举办一场擂台游戏，如果共有 2k 名选手参加，那么游戏分为 k 轮进行：
• 第一轮编号为 1, 2 的选手进行一次对局，编号为 3, 4 的选手进行一次对局，以此
类推，编号为 2k − 1, 2k 的选手进行一次对局。
• 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
• 以此类推，第 k − 1 轮在只保留第 k − 2 轮的 4 位胜者的前提下，前两位、后两
位分别进行对局，也就是所谓的半决赛。
• 第 k 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选
手都有一个能力值 a1, a2, · · · , a2k
，能力值为 [0, 231 − 1] 之内的整数。对于每场比赛，会
先抽签决定一个数 0/1，我们将第 R 轮的第 G 场比赛抽到的数记为 dR,G。抽到 0 则表
示表示编号小的选手为擂主，抽到 1 则表示编号大的选手为擂主。擂主获胜当且仅当他
的能力值 a ≥ R。也就是说，游戏的胜负只取决于擂. 主. 的. 能. 力. 值. 与当. 前. 比. 赛. 是. 第. 几. 轮. 的
大小关系，与. 另. 一. 位. 的. 能. 力. 值. 无. 关. 。
现在，小 S 先后陆续收到了 n 位选手的报名信息，他们分别告知了小 S 自己的能
力值。小 S 会按照报名的先后顺序对选手进行编号为 1, 2, · · · , n。小 S 关心的是，补充
尽. 量. 少. 的选手使总人数为 2 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可
能成为总冠军的选手的编. 号. 之. 和. 为多少。
形式化地，设 k 是最小的非负整数使得 2 k ≥ n，那么应当补充 (2k − n) 名选手，且
补充的选手的能力值可以任取 [0, 231 − 1] 之内的整数。如. 果. 补. 充. 的. 选. 手. 有. 可. 能. 获. 胜，. 也.
应. 当. 计. 入. 答. 案. 中. 。
当然小 S 觉得这个问题还是太简单了，所以他给了你 m 个询问 c1, c2, · · · , cm。小
S 希望你帮忙对于每个 ci 求出，在只收到前 ci 位选手的报名信息时，这个问题的答案
是多少。

Input

从文件 arena.in 中读入数据。
本. 题. 的. 测. 试. 点. 包. 含. 有. 多. 组. 测. 试. 数. 据. ，但不同测试数据只是通过修改 a1, a2, · · · , an 得
到，其他内容均保持不变，请参考以下格式。其中 ⊕ 代表异或运算符，a mod b 代表 a
除以 b 的余数。
输入的第一行包含两个正整数 n, m，表示报名的选手数量和询问的数量。
输入的第二行包含 n 个非负整数 a1′  , a2′  , · · · , an′ ，这列数将用来计算真正的能力值。
输入的第三行包含 m 个正整数 c1, c2, · · · , cm，表示询问。
设 K 是使得 2 K ≥ n 的最小的非负整数，接下来的 K 行当中，第 R 行包含 2 K−R

个数（无空格），其中第 G 个数表示第 R 轮的第 G 场比赛抽签得到的 dR,G = 0/1。

注意，由于询问只是将人数凑齐到 2k ≥ ci，这里的 k ≤ K，因此你未必会用到全部

的输入值。
接下来一行包含一个正整数 T，表示有 T 组测试数据。
接下来共 T 行，每行描述一组数据，包含 4 个非负整数 X0, X1, X2, X3，该组数据
的能力值 ai = ai′  ⊕ Xi mod 4，其中 1 ≤ i ≤ n 。

Output

输出到文件 arena.out 中。
共输出 T 行，对于每组数据，设 Ai 为第 i（1 ≤ i ≤ m）组询问的答案，你只需要
输出一行包含一个整数，表示 (1 × A1) ⊕ (2 × A2) ⊕ · · · ⊕ (m × Am) 的结果。

Sample Input Copy 

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

Sample Output Copy 

5
19
7
1

HINT

【样例 1 解释】
共有 T = 4 组数据，这里只解释第一组。5 名选手的真实能力值为 [1, 0, 0, 2, 1]。5
组询问分别是对长度为 5, 4, 1, 2, 3 的前缀进行的。
1. 对于长度为 1 的前缀，由于只有 1 号一个人，因此答案为 1。
2. 对于长度为 2 的前缀，由于 2 个人已经是 2 的幂次，因此不需要进行扩充。根据
抽签 d1
,
1 = 1 可知 2 号为擂主，由于 a2 < 1，因此 1 号获胜，答案为 1。
3. 对于长度为 3 的前缀，首先 1 号、2 号比赛是 1 号获胜（因为 d1,1 = 1，故 2 号
为擂主，a2 < 1），然后虽然 4 号能力值还不知道，但 3 号、4 号比赛一定是 4 号
获胜（因为 d1,2 = 0，故 3 号为擂主，a3 < 1），而决赛 1 号、4 号谁获胜都有可
能（因为 d2,1 = 1，故 4 号为擂主，如果 a4 < 2 则 1 号获胜，a4 ≥ 2 则 4 号获
胜）。综上所述，答案为 1 + 4 = 5。
4. 对于长度为 4 的前缀，我们根据上一条的分析得知，由于 a4 ≥ 2 ，所以决赛获
胜的是 4 号。
5. 对于长度为 5 的前缀，可以证明，可能获胜的选手包括 4 号、7 号、8 号，答案
为 19。
因此，该组测试数据的答案为 (1 × 19) ⊕ (2 × 4) ⊕ (3 × 1) ⊕ (4 × 1) ⊕ (5 × 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 ≤ n, m ≤ 105，0 ≤ ai , Xj < 231，1 ≤ ci ≤ n，1 ≤ T ≤ 256。


特殊性质 A：保证询问的 ci 均为 2 的幂次。
特殊性质 B：保证所有的 dR,G = 0。

Source/Category