题目背景
『博』和『奕』喜欢博弈,尤其喜欢 wqs 带权博弈。
题目描述
wqs 带权博弈在一个数列 {ai} 上进行,对应有一个 01 串 {bi}。
- 若 bi=0,则 ai 这个数字是属于『博』的;
- 若 bi=1,则 ai 这个数字是属于『奕』的。
游戏规则是,每次给定一个区间 [l,r],从 al 到 ar,拥有这个数的人依次决定选该数或者不选,两个人都会采用最优策略。
因为『博』很强大,她会让着『奕』,于是博弈的规则是,如果最后两个人选的数按位异或和不为零,则『奕』获胜,否则『博』获胜。
注意每个人能看到对方的选数情况,可以选多个数(只要这个数是自己的),最后计算两个人选数的总异或和。
对于任意区间 [l,r],若『奕』获胜,则 w(l,r)=1,否则 w(l,r)=0。
每次查询 l=L∑Rr=l∑Rw(l,r) 的值,对 232 取模。
由于输入输出量过大,对于 tp=0 的测试点,选手需要自行生成数列 ai 和询问区间 [L,R],并用特殊方式输出答案。
注意正解不依赖特殊的输入输出方式。
输入格式
第一行三个正整数 n,q,tp,表示数列长度,天数以及每天局数,以及读入方式。
第二行一个长度为 n 的字符串,表示 01 串 {bi};
若 tp=0,则第三行 n 个正整数,表示数列 {ai},接下来 q 行,每行两个正整数 L,R,表示询问 l=L∑Rr=l∑Rw(l,r) 对 232 取模的值。
否则,令 Sd
初值为 tp,Cnt
初值为 0,先使用函数 GetA
依次生成 ai,再使用函数 GetLR
依次生成 L,R,具体方式以代码形式后附。
输出格式
若 tp=0 则输出 q 行,每行一个正整数,表示该询问的答案。
否则,令 ansi 为第 i 次询问的答案,你需要输出 (ansi×i)mod232 的按位异或和。
提示
【样例解释 #1】
只有 w(1,1)=w(1,2)=1。
对于区间 [1,3],如果『奕』选第一个数,则『博』选后两个数,否则『博』不选,于是『博』获胜。
注意是从左往右依次选取,『博』在选后两个数之前能够知道『奕』是否选了第一个数。
【样例解释 #2】
只有 w(1,1)=w(1,2)=w(1,3)=w(1,4)=w(2,3)=w(2,4)=w(3,3)=w(3,4)=1。
【样例解释 #3】
由于本样例 tp=0,所以你需要使用特殊方式输入输出。
【数据范围】
对于所有数据,1≤n≤5×105,1≤q≤1.5×106,0<ai<260,1≤L≤R≤n,0≤tp<264。
子任务编号 |
分值 |
n≤ |
q≤ |
tp |
ai< |
特殊性质 |
1 |
6 |
20 |
100 |
=0 |
260 |
有 |
2 |
7 |
100 |
103 |
210 |
3 |
8 |
700 |
无 |
4 |
9 |
3000 |
105 |
260 |
5 |
14 |
3×104 |
220 |
6 |
17 |
2×105 |
1.5×106 |
≥1 |
260 |
有 |
7 |
19 |
5×105 |
8 |
20 |
无 |
特殊性质:序列 bi 中最多有 10 个 0。
【备注】
数据生成方式: