Background

And thus it is Tairitsu's turn to gain the upper hand.

Problem Description

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$). You need to count 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$.

Tip: The total time limit for this problem is relatively large, so please reduce meaningless submissions (such as high-complexity brute force, or directly submitting the provided but still incomplete code, etc.).

Input Format

Because the amount of data in this problem is large, you do not need to perform input/output. Please complete the init(int, int, vector<int>) and solve(int, int) functions in the following program and submit. The correct solution does not depend on this template.

#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

Hint

Data Size and Constraints

For $100\%$ of the testdata, $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$.

For $100\%$ of the testdata, the input is valid.

• Subtask 1 (5 pts, Tutorial): $1\le n,q\le 10^2$.
• Subtask 2 (7 pts, Tutorial): $1\leq n,q\leq 10^3$.
• Subtask 3 (11 pts, PST 5.0): $1\leq n,q\leq 10^4$.
• Subtask 4 (17 pts, PRS 8.2): $1\leq n,q\leq 10^5$.
• Subtask 5 (61 pts, FTR 10.8): $1\leq n\le 6\times 10^5,1\le q\leq 10^6$.

Why are there multiple $1$ points? Because the chart author got $1$ Lost when playing this song.

Idea: Powerless; Solution: ccz181078&noip&w33z; Code: w33z; Data: w33z.

This problem was added on 2022.4.10. Thanks for their help.

The data was strengthened on 2022.4.27 by w33z.

2022.4.10 - 2022.5.4: 25 days 1st kill (水军带你飞, Shui Jun Dai Ni Fei).

2022.4.10 - 2022.5.17: 38 days 2nd kill (WhisperingSnowflakes).

2022.4.10 - 2022.6.9: 61 days 3rd kill (Verdandi).

Translated by ChatGPT 5