Problem D: 擂台游戏

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：3 Solved：1

Description

小 S 想要举办一场擂台游戏，如果共有 2^k 名选手参加，那么游戏分为 k 轮进行：
  • 第一轮编号为 1，2 的选手进行一次对局，编号为 3，4 的选手进行一次对局，以此类推，编号为 2^k−12^k 的选手进行一次对局。
  • 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
  • 以此类推，第 k−1 轮在只保留第 k−2 轮的 4 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
  • 第 k 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 a1， a2， …a2^k，能力值为 [0，2^31 −1] 之内的整数。对于每场比赛，会先抽签决定一个数 0/1，我们将第 R 轮的第 G 场比赛抽到的数记为 dR，G 。抽到 0 则表示表示编号小的选手为擂主，抽到 1 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 a≥R。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。

现在，小 S 先后陆续收到了 n 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 1，2…n。小 S 关心的是，补充尽量少的选手使总人数为 2 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和是多少。

形式化地，设 k 是最小的非负整数使得 2^k ≥n，那么应当补充 (2^k −n) 名选手，且补充的选手的能力值可以任取 [0，2^31 −1] 之内的整数。如果补充的选手有可能取胜，也应当计入答案中。

当然小 S 觉得这个问题还是太简单了，所以他给了你 m 个询问 c1， c2 ，…cm 。小 S 希望你帮忙对于每个 ci 求出，在只收到前 ci 位选手的报名信息时，这个问题的答案是多少。


【数据范围】
对于所有测试数据，保证：2≤nm≤10^5 ，0≤ai Xj <2^31 ，1≤ci ≤n，1≤T≤256。

Input

本题的测试点包含有多组测试数据。 但不同测试数据只是通过修改 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 场比赛抽签得到的 d R,G =0/1。
注意，由于询问只是将人数凑齐到 2^k≥ci ，这里的 k≤K，因此你未必会用到全部的输入值。
接下来一行包含一个正整数 T，表示有 T 组测试数据。
接下来共 T 行，每行描述一组数据，包含 4 个非负整数 X0 ,X1 ,X2 ,X3 ，该组数据的能力值 ai =ai′⊕Xi mod 4 ，其中 1≤i≤n。

Output

共输出 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. 对于长度为  的前缀，由于只有  号一个人，因此答案为 。
  2. 对于长度为  的前缀，由于  个人已经是  的幂次，因此不需要进行扩充。根据抽签  可知  号为擂主，由于 ，因此  号获胜，答案为 。
  3. 对于长度为  的前缀，首先  号、 号比赛是  号获胜（因为 ，故  号为擂主，），然后虽然  号能力值还不知道，但  号、 号比赛一定是  号获胜（因为 ，故  号为擂主，），而决赛  号、 号谁获胜都有可能（因为 ，故  号为擂主，如果  则  号获胜， 则  号获胜）。综上所述，答案为 。
  4. 对于长度为  的前缀，我们根据上一条的分析得知，由于  ，所以决赛获胜的是  号。
  5. 对于长度为  的前缀，可以证明，可能获胜的选手包括  号、 号、 号，答案为 。

因此，该组测试数据的答案为 。

Source/Category

Return to contestSubmitSubmit RecordShowOff!