P8283 "MCOI-08" Dantalion
Background
And thus it is Tairitsu's turn to gain the upper hand.
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
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)` and `solve(int, int)` functions in the following program and submit. The correct solution does not depend on this 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
Output Format
N/A
Explanation/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