#P13963. [2024多校联盟省选模拟]卡牌游戏

    ID: 13175 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700博弈论线段树数学可持久化前缀和数据结构线性基

[2024多校联盟省选模拟]卡牌游戏

题目描述

小 A 和小 B 在玩一个游戏:

现在有 nn 张卡牌,第 ii 张卡牌上写了 aia_i,其中 ai∈[0,2m−1]a_i \in [0,2^m-1]。

游戏开始时两个人手上都没有卡牌,然后小 A 先手,两人轮流操作,每次取走一张卡牌。

  • 小 A 的目的是最大化自己最后所有卡牌数字的按位异或和;
  • 小 B 的目的是最小化小 A 最终手牌的按位异或和。

有 qq 次游戏,每次取出一个区间 [l,r][l,r] 来进行游戏。你需要输出:该次游戏结束后,小 A 所有卡牌数字异或和中,最高位为 00 的出现位置。

定义从低位到高位依次为第 11 位到第 mm 位;如果不存在(即所有位都是 11),则输出 00。

输入格式

第一行三个数 c,n,mc,n,m,cc 代表测试点编号。
第二行 nn 个数表示 a1,…,ana_1,\ldots,a_n。
第三行一个数 qq 表示询问次数。
接下来 qq 行,每行两个整数 l,rl,r 表示询问区间。

输出格式

输出 qq 行,第 ii 行输出第 ii 次询问的答案。

1 5 2
1 3 2 2 1
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
0
1
0
2
0
2
0
1
0
1

样例解释

  • l=1,r=2l=1,r=2 时,小 A 取 33 即可,答案为 33。因为 33 的每一位都是 11,所以输出 00。
  • l=1,r=3l=1,r=3 时,小 A 先取 11,小 B 必取 22,小 A 再取 33,最终异或和为 22。因为 22 的最低位为 00,故输出 11。

数据范围与提示

测试点编号 n≤n\le m≤m\le q≤q\le 特殊性质
1∼31\sim 3 10 10510^5
4∼64\sim 6 3×1053\times 10^5 1 3×1053\times 10^5
7∼97\sim 9 2
10∼1210\sim 12 4
13∼1513\sim 15 10 A
16∼1916\sim 19
20∼2520\sim 25 20
  • 特殊性质 A:保证 l=1l=1。
  • 下发的第 ii 个大样例满足第 ii 种测试点限制;也可通过大样例的 cc 判断属于哪一类测试点。
  • 对于所有数据:0≤n,q≤3×1050\le n,q\le 3\times 10^5,1≤m≤201\le m\le 20,0≤ai≤2m−10\le a_i\le 2^m-1。