「Cfz Round 1」Wqs Game

『博』和『奕』喜欢博弈，尤其喜欢 wqs 带权博弈。

wqs 带权博弈在一个数列 $\{a_i\}$ 上进行，对应有一个 $01$ 串 $\{b_i\}$。 1. 若 $b_i=0$，则 $a_i$ 这个数字是属于『博』的； 2. 若 $b_i=1$，则 $a_i$ 这个数字是属于『奕』的。 游戏规则是，每次给定一个区间 $[l,r]$，从 $a_l$ 到 $a_r$，拥有这个数的人**依次**决定选该数或者不选，两个人都会采用**最优策略**。 因为『博』很强大，她会让着『奕』，于是博弈的规则是，如果最后两个人选的数**按位异或和不为零**，则『奕』获胜，否则『博』获胜。 注意每个人**能看到**对方的选数情况，可以选**多个**数（只要这个数是自己的），最后计算两个人选数的总**异或**和。 对于任意区间 $[l,r]$，若『奕』获胜，则 $w(l,r)=1$，否则 $w(l,r)=0$。 每次查询 $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ 的值，对 $2^{32}$ 取模。 由于输入输出量过大，对于 $tp\ne 0$ 的测试点，选手需要自行生成数列 $a_i$ 和询问区间 $[L,R]$，并用特殊方式输出答案。 注意正解**不依赖**特殊的输入输出方式。

第一行三个正整数 $n,q,tp$，表示数列长度，天数以及每天局数，以及读入方式。 第二行一个长度为 $n$ 的字符串，表示 $01$ 串 $\{b_i\}$； 若 $tp=0$，则第三行 $n$ 个正整数，表示数列 $\{a_i\}$，接下来 $q$ 行，每行两个正整数 $L,R$，表示询问 $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ 对 $2^{32}$ 取模的值。 否则，令 `Sd` 初值为 $tp$，`Cnt` 初值为 $0$，先使用函数 `GetA` 依次生成 $a_i$，再使用函数 `GetLR` 依次生成 $L,R$，具体方式以代码形式后附。

若 $tp=0$ 则输出 $q$ 行，每行一个正整数，表示该询问的答案。 否则，令 $ans_i$ 为第 $i$ 次询问的答案，你需要输出 $(ans_i\times i)\bmod 2^{32}$ 的**按位异或和**。

3 2 0
100
3 1 2
1 3
2 3

2
0

5 2 0
10100
2 7 6 3 5
1 5
2 4

8
4

20 100 8551679995685981130
11001000000000000000

1673

#### 【样例解释 #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\ne 0$，所以你需要使用特殊方式输入输出。 #### 【数据范围】 对于所有数据，$1\le n\le5\times10^5,1\le q\le 1.5\times10^6,0<a_i<2^{60},1\le L\le R\le n,0\le tp<2^{64}$。 | 子任务编号 | 分值 | $n\le$ | $q\le$ | $tp$ | $a_i<$ | 特殊性质 | | :--------: | :--: | :-----------: | :-------------: | :----: | :------: | :------: | | $1$ | $6$ | $20$ | $100$ | $=0$ | $2^{60}$ | 有 | | $2$ | $7$ | $100$ | $10^3$ | $=0$ | $2^{10}$ | 有 | | $3$ | $8$ | $700$ | $10^3$ | $=0$ | $2^{10}$ | 无 | | $4$ | $9$ | $3000$ | $10^5$ | $=0$ | $2^{60}$ | 无 | | $5$ | $14$ | $3\times10^4$ | $10^5$ | $=0$ | $2^{20}$ | 无 | | $6$ | $17$ | $2\times10^5$ | $1.5\times10^6$ | $\ge1$ | $2^{60}$ | 有 | | $7$ | $19$ | $5\times10^5$ | $1.5\times10^6$ | $\ge1$ | $2^{60}$ | 有 | | $8$ | $20$ | $5\times10^5$ | $1.5\times10^6$ | $\ge1$ | $2^{60}$ | 无 | 特殊性质：序列 $b_i$ 中最多有 $10$ 个 $0$。 #### 【备注】 数据生成方式： ```cpp using ul=unsigned long long; using ui=unsigned int; ui Ans,ans; ul Sd,Cnt; ul Rd(){Sd^=Sd<<19,Sd^=Sd>>12,Sd^=Sd<<29;return Sd^=++Cnt;} void GetA(ul &a){a=Rd()%((1ull<<60)-2)+1;} void GetLR(int &l,int &r){ l=Rd()%n+1,r=Rd()%n+1; if(l>r)swap(l,r); } int main(){ //read n,q,tp,b[i] if(tp){ Sd=tp,Cnt=0; for(int i=1;i<=n;++i)GetA(a[i]); for(int qi=1;qi<=q;++qi){ GetLR(l,r); //sol Ans^=ans*qi; } printf("%u\n",Ans); } } ```