P8337 [Ynoi2004] rsxc

You are given a non-negative integer sequence $a_0, a_1, \dots, a_{n-1}$ of length $n$ ($1 \le n \le 6 \times 10^5$), where $0 \le a_i < 2^{30}$. There are $q$ queries ($1 \le q \le 10^6$). Each query gives two integers $l, r$ ($0 \le l \le r < n$). Find how many pairs of integers $(x, y)$ satisfy: - $l \le x \le y \le r$; - $\forall i, j \in S: i \oplus j \in S$, where $S := \{a_k\}_{k=x}^y$.

Since the amount of data is large, you do not need to do input/output. Please complete the `init(int, int, vector)` and `solve(int, int)` functions in the following program and submit it. The correct solution does not depend on the template. ```cpp #include using namespace std; void init(int n, int q, vector 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 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

N/A

Idea: Powerless. Solution: ccz181078 & nzhtl1477 & w33z. Code: w33z. Data: w33z. For $100\%$ of the testdata, $1 \le n \le 6 \times 10^5$, $1 \le q \le 10^6$, $0 \le a_i < 2^{30}$, and $0 \le l \le r < n$. Translated by ChatGPT 5