「MCOI-08」Dantalion
题目背景
And thus it is Tairitsu's turn to gain the upper hand.
题目描述
给定一个长为 $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$。
Tip: 本题总时限较大，故请减少无意义提交量（如高复杂度暴力或是直接提交所给尚需完善的代码等）。
输入输出格式
输入格式
由于本题数据较多，您不需要输入输出，请完善以下程序中的 `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;
}
```
输出格式
输入输出样例
输入样例 #1
5 10 2
0000000001000020000300004输出样例 #1
4834712607666044912输入样例 #2
20 100 16500242824326557842
0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>输出样例 #2
5449866856465492064说明
#### 数据规模与约定
对于 $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$。
对于 $100\%$ 的数据，输入合法。
- 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.9~~）：$1\leq n\le 6\times 10^5,1\le q\leq 10^6$。
为什么要多个 $1$ 分呢，因为谱师打本曲时性了 $1$ Lost.
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 (水军带你飞).
2022.4.10 - 2022.5.17 : 38 days 2nd kill (WhisperingSnowflakes).
2022.4.10 - 2022.6.9 : 61 days 3rd kill (Verdandi).