{"problem":{"name":"[Ynoi2004] rsxc","description":{"content":"给定一个长为 $n$（$1\\le n\\le 6\\times 10^5$）的非负整数序列 $a_0,a_1,\\dots,a_{n-1}$（$0\\le a_i<2^{30}$）。 有 $q$ 个询问（$1\\le q\\le 10^6$）。 每次询问给出两个整数 $l,r$（$0\\le l\\le r<n$），求有多少对整数 $(x,y)$ 满足：  - $l\\le x\\le y\\le r$；  - ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8337"},"statements":[{"statement_type":"Markdown","content":"给定一个长为 $n$（$1\\le n\\le 6\\times 10^5$）的非负整数序列 $a_0,a_1,\\dots,a_{n-1}$（$0\\le a_i<2^{30}$）。\n\n有 $q$ 个询问（$1\\le q\\le 10^6$）。\n\n每次询问给出两个整数 $l,r$（$0\\le l\\le r<n$），求有多少对整数 $(x,y)$ 满足：\n\n - $l\\le x\\le y\\le r$；\n - $\\forall i,j\\in S\\ :i\\oplus j\\in S$，其中 $S:=\\{a_k\\}_{k=x}^y$。\n\n## Input\n\n由于本题数据较多，您不需要输入输出，请完善以下程序中的 `init(int, int, vector<int>)` 和 `solve(int, int)` 函数，并提交。正解不依赖于其模板。\n\n```cpp\n#include <bits/stdc++.h>\nusing namespace std;\n\nvoid init(int n, int q, vector<int> a) {\n  // implement...\n}\n\nlong long solve(int l, int r) {\n  // implement...\n}\n\nint main() {\n  int n, q;\n  uint64_t s;\n  cin >> n >> q >> s;\n  string r;\n  cin >> r;\n  vector<int> a(n);\n  for (int i = 0; i < n; i++)\n    for (int s = 5 * i; s < 5 * i + 5; s++)\n      a[i] = (a[i] * 64 + (int)(r[s]) - (int)('0'));\n  init(n, q, a);\n  uint64_t state = 0;\n  auto splitmix64 = [&](uint64_t v) {\n    uint64_t z = (v + 0x9e3779b97f4a7c15);\n    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;\n    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;\n    return z ^ (z >> 31);\n  };\n  mt19937_64 rng(s);\n  for (int i = 0; i < q; i++) {\n    int l = (rng() ^ state) % n;\n    int r = (rng() ^ state) % n;\n    long long ans = solve(min(l, r), max(l, r));\n    state = splitmix64(state + ans);\n    if ((i + 1) % (1 << 15) == 0)\n      cout << state << endl;\n  }\n  cout << state << endl;\n}\n```\n\n[samples]\n\n## Note\n\nIdea：Powerless，Solution：ccz181078&nzhtl1477&w33z，Code：w33z，Data：w33z\n\n对于 $100\\%$ 的数据，$1\\leq n\\le 6\\times 10^5,1\\le q\\leq 10^6$，$0 \\le a_i < 2^{30}$，$0 \\le l \\le r < n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8337","tags":["2004","O2优化","Ynoi"],"sample_group":[["5 10 2\n0000000001000020000300004","4834712607666044912"],["20 100 16500242824326557842\n0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>","5449866856465492064"]],"created_at":"2026-03-03 11:09:25"}}