{"problem":{"name":"「Cfz Round 1」Wqs Game","description":{"content":"wqs 带权博弈在一个数列 $\\{a_i\\}$ 上进行，对应有一个 $01$ 串 $\\{b_i\\}$。 1. 若 $b_i=0$，则 $a_i$ 这个数字是属于『博』的； 2. 若 $b_i=1$，则 $a_i$ 这个数字是属于『奕』的。 游戏规则是，每次给定一个区间 $[l,r]$，从 $a_l$ 到 $a_r$，拥有这个数的人**依次**决定选该数或者不选，两个人都会采用**最优策略**。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1200,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9580"},"statements":[{"statement_type":"Markdown","content":"wqs 带权博弈在一个数列 $\\{a_i\\}$ 上进行，对应有一个 $01$ 串 $\\{b_i\\}$。\n\n1. 若 $b_i=0$，则 $a_i$ 这个数字是属于『博』的；\n2. 若 $b_i=1$，则 $a_i$ 这个数字是属于『奕』的。\n\n游戏规则是，每次给定一个区间 $[l,r]$，从 $a_l$ 到 $a_r$，拥有这个数的人**依次**决定选该数或者不选，两个人都会采用**最优策略**。\n\n因为『博』很强大，她会让着『奕』，于是博弈的规则是，如果最后两个人选的数**按位异或和不为零**，则『奕』获胜，否则『博』获胜。\n\n注意每个人**能看到**对方的选数情况，可以选**多个**数（只要这个数是自己的），最后计算两个人选数的总**异或**和。\n\n对于任意区间 $[l,r]$，若『奕』获胜，则 $w(l,r)=1$，否则 $w(l,r)=0$。\n\n每次查询 $\\sum\\limits_{l=L}^R\\sum\\limits_{r=l}^Rw(l,r)$ 的值，对 $2^{32}$ 取模。\n\n由于输入输出量过大，对于 $tp\\ne 0$ 的测试点，选手需要自行生成数列 $a_i$ 和询问区间 $[L,R]$，并用特殊方式输出答案。\n\n注意正解**不依赖**特殊的输入输出方式。\n\n## Input\n\n第一行三个正整数 $n,q,tp$，表示数列长度，天数以及每天局数，以及读入方式。\n\n第二行一个长度为 $n$ 的字符串，表示 $01$ 串 $\\{b_i\\}$；\n\n若 $tp=0$，则第三行 $n$ 个正整数，表示数列 $\\{a_i\\}$，接下来 $q$ 行，每行两个正整数 $L,R$，表示询问  $\\sum\\limits_{l=L}^R\\sum\\limits_{r=l}^Rw(l,r)$ 对 $2^{32}$ 取模的值。\n\n否则，令 `Sd` 初值为 $tp$，`Cnt` 初值为 $0$，先使用函数 `GetA` 依次生成 $a_i$，再使用函数 `GetLR` 依次生成 $L,R$，具体方式以代码形式后附。\n\n## Output\n\n若 $tp=0$ 则输出 $q$ 行，每行一个正整数，表示该询问的答案。\n\n否则，令 $ans_i$ 为第 $i$ 次询问的答案，你需要输出 $(ans_i\\times i)\\bmod 2^{32}$ 的**按位异或和**。\n\n[samples]\n\n## Background\n\n『博』和『奕』喜欢博弈，尤其喜欢 wqs 带权博弈。\n\n## Note\n\n#### 【样例解释 #1】\n\n只有 $w(1,1)=w(1,2)=1$。\n\n对于区间 $[1,3]$，如果『奕』选第一个数，则『博』选后两个数，否则『博』不选，于是『博』获胜。\n\n注意是从左往右依次选取，『博』在选后两个数之前能够知道『奕』是否选了第一个数。\n\n#### 【样例解释 #2】\n\n只有 $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$。\n\n#### 【样例解释 #3】\n\n由于本样例 $tp\\ne 0$，所以你需要使用特殊方式输入输出。\n\n#### 【数据范围】\n\n对于所有数据，$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\n| 子任务编号 | 分值 |    $n\\le$     |     $q\\le$      |  $tp$  |  $a_i<$  | 特殊性质 |\n| :--------: | :--: | :-----------: | :-------------: | :----: | :------: | :------: |\n|    $1$     | $6$  |     $20$      |      $100$      |  $=0$  | $2^{60}$ |    有    |\n|    $2$     | $7$  |     $100$     |     $10^3$      |  $=0$  | $2^{10}$ |    有    |\n|    $3$     | $8$  |     $700$     |     $10^3$      |  $=0$  | $2^{10}$ |    无    |\n|    $4$     | $9$  |    $3000$     |     $10^5$      |  $=0$  | $2^{60}$ |    无    |\n|    $5$     | $14$ | $3\\times10^4$ |     $10^5$      |  $=0$  | $2^{20}$ |    无    |\n|    $6$     | $17$ | $2\\times10^5$ | $1.5\\times10^6$ | $\\ge1$ | $2^{60}$ |    有    |\n|    $7$     | $19$ | $5\\times10^5$ | $1.5\\times10^6$ | $\\ge1$ | $2^{60}$ |    有    |\n|    $8$     | $20$ | $5\\times10^5$ | $1.5\\times10^6$ | $\\ge1$ | $2^{60}$ |    无    |\n\n特殊性质：序列 $b_i$ 中最多有 $10$ 个 $0$。\n\n#### 【备注】\n\n数据生成方式：\n\n```cpp\nusing ul=unsigned long long;\nusing ui=unsigned int;\nui Ans,ans;\nul Sd,Cnt;\nul Rd(){Sd^=Sd<<19,Sd^=Sd>>12,Sd^=Sd<<29;return Sd^=++Cnt;}\nvoid GetA(ul &a){a=Rd()%((1ull<<60)-2)+1;}\nvoid GetLR(int &l,int &r){\n    l=Rd()%n+1,r=Rd()%n+1;\n    if(l>r)swap(l,r);\n}\nint main(){\n    //read n,q,tp,b[i]\n    if(tp){\n        Sd=tp,Cnt=0;\n        for(int i=1;i<=n;++i)GetA(a[i]);\n        for(int qi=1;qi<=q;++qi){\n            GetLR(l,r);\n            //sol\n            Ans^=ans*qi;\n        }\n        printf(\"%u\\n\",Ans);\n\t}\n}\n```","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9580","tags":["树状数组","洛谷原创","O2优化","线性基","洛谷月赛","单调栈"],"sample_group":[["3 2 0\n100\n3 1 2\n1 3\n2 3","2\n0"],["5 2 0\n10100\n2 7 6 3 5\n1 5\n2 4","8\n4"],["20 100 8551679995685981130\n11001000000000000000","1673"]],"created_at":"2026-03-03 11:09:25"}}