[Ynoi2004] rsxc

给定一个长为 $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$； - $\forall i,j\in S\ :i\oplus j\in S$，其中 $S:=\{a_k\}_{k=x}^y$。

由于本题数据较多，您不需要输入输出，请完善以下程序中的 `init(int, int, vector<int>)` 和 `solve(int, int)` 函数，并提交。正解不依赖于其模板。 ```cpp #include <bits/stdc++.h> using namespace std; void init(int n, int q, vector<int> a) { // implement... } long long solve(int l, int r) { // implement... } int main() { int n, q; uint64_t s; cin >> n >> q >> s; string r; cin >> r; vector<int> a(n); for (int i = 0; i < n; i++) for (int s = 5 * i; s < 5 * i + 5; s++) a[i] = (a[i] * 64 + (int)(r[s]) - (int)('0')); init(n, q, a); uint64_t state = 0; auto splitmix64 = [&](uint64_t v) { uint64_t z = (v + 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; return z ^ (z >> 31); }; mt19937_64 rng(s); for (int i = 0; i < q; i++) { int l = (rng() ^ state) % n; int r = (rng() ^ state) % n; long long ans = solve(min(l, r), max(l, r)); state = splitmix64(state + ans); if ((i + 1) % (1 << 15) == 0) cout << state << endl; } cout << state << endl; } ```

5 10 2
0000000001000020000300004

4834712607666044912

20 100 16500242824326557842
0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>

5449866856465492064

Idea：Powerless，Solution：ccz181078&noip&w33z，Code：w33z，Data：w33z 对于 $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$。