题目描述
【题目描述】
小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是最小的非负整数使得2k≥n，那么应当补充(2k−n)名选手，补充的选手的能力值可以任取[0,231−1]之内的整数。.如果补充的选手有可能获胜， 也应当计入答案中。
当然小S觉得这个问题还是太简单了，所以他给了你m个询问c1,c2,··· ,cm。小S希望你帮忙对于每个ci 求出，在只收到前ci 位选手的报名信息时，这个问题的答案 是多少。
小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是最小的非负整数使得2k≥n，那么应当补充(2k−n)名选手，补充的选手的能力值可以任取[0,231−1]之内的整数。.如果补充的选手有可能获胜， 也应当计入答案中。
当然小S觉得这个问题还是太简单了，所以他给了你m个询问c1,c2,··· ,cm。小S希望你帮忙对于每个ci 求出，在只收到前ci 位选手的报名信息时，这个问题的答案 是多少。
输入
本题的测试点包含有多组测试数据，但不同测试数据只是通过修改 a1,a2,··· ,an 得到，其他内容均保持不变，请参考以下格式。其中⊕代表异或运算符，a mod b代表a
除以b的余数。
输入的第一行包含两个正整数n,m，表示报名的选手数量和询问的数量。
输入的第二行包含n个非负整数a′ 1,a′ 2,··· ,a′ n，这列数将用来计算真正的能力值。
输入的第三行包含m个正整数c1,c2,··· ,cm，表示询问。
设K是使得2K≥n的最小的非负整数，接下来的K行当中，第R行包含2K−R 个数（无空格），其中第G个数表示第R轮的第G场比赛抽签得到的dR,G=0/1。
注意，由于询问只是将人数凑齐到2k≥ci，这里的k≤K，因此你未必会用到全部的输入值。
接下来一行包含一个正整数T，表示有T组测试数据。 接下来共T行，每行描述一组数据，包含4个非负整数X0,X1,X2,X3，该组数据 的能力值ai=a′ i ⊕ Xi mod 4，其中1≤i≤n。
输入的第一行包含两个正整数n,m，表示报名的选手数量和询问的数量。
输入的第二行包含n个非负整数a′ 1,a′ 2,··· ,a′ n，这列数将用来计算真正的能力值。
输入的第三行包含m个正整数c1,c2,··· ,cm，表示询问。
设K是使得2K≥n的最小的非负整数，接下来的K行当中，第R行包含2K−R 个数（无空格），其中第G个数表示第R轮的第G场比赛抽签得到的dR,G=0/1。
注意，由于询问只是将人数凑齐到2k≥ci，这里的k≤K，因此你未必会用到全部的输入值。
接下来一行包含一个正整数T，表示有T组测试数据。 接下来共T行，每行描述一组数据，包含4个非负整数X0,X1,X2,X3，该组数据 的能力值ai=a′ i ⊕ Xi mod 4，其中1≤i≤n。
输出
共输出T行，对于每组数据，设Ai为第i（1≤i≤m）组询问的答案，你只需要输出一行包含一个整数，表示(1×A1)⊕(2×A2)⊕···⊕(m×Am)的结果。
样例输入 复制
55
0 0 0 0 0
5 4 1 2 3
1 0 0 1
1 0
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 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的幂次，因此不需要进行扩充。根据 抽签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≤n,m≤100000，0≤ai,Xj <231，1≤ci ≤n，1≤T ≤256。
特殊性质A：保证询问的ci均为2的幂次。
特殊性质B：保证所有的dR,G=0。
共有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≤n,m≤100000，0≤ai,Xj <231，1≤ci ≤n，1≤T ≤256。
|
测试点 |
T= |
n,m≤ |
特殊性质A |
特殊性质B |
| 1~3 | 1 | 8 |
否 |
否 |
| 4、5 | 1 | 500 |
是 |
否 |
| 6~8 | 1 |
500 |
否 |
是 |
| 9,10 | 1 |
5000 |
否 |
否 |
| 11,12 | 1 | 100000 |
是 |
否 |
| 13~15 | 1 |
100000 |
否 |
是 |
| 16,17 | 4 |
100000 |
否 |
否 |
| 18,19 | 16 |
100000 |
否 |
否 |
| 20,21 | 64 |
100000 |
否 |
否 |
| 22,23 | 128 |
100000 |
否 |
否 |
| 24,25 | 256 |
100000 |
否 |
否 |
特殊性质A：保证询问的ci均为2的幂次。
特殊性质B：保证所有的dR,G=0。