P11283 「GFOI Round 2」Turtle and Nediam

For a sequence $a$ of distinct positive integers with length $|a| \geq 3$, the "nediam" $f(a)$ is defined as follows: - When $|a| = 3$, $f(a)$ is the median of $a$; - When $|a| > 3$, for any contiguous subsequence of length $3$ denoted as $[a_i, a_{i + 1}, a_{i + 2}]$, let the median of this subsequence be $x$. The sequence obtained by removing $x$ from $a$ is denoted as $b$, and $f(a)$ is the maximum value of $f(b)$ over all such subsequences. Turtle gives you a permutation $p_1, p_2, \ldots, p_n$ of the integers from $1$ to $n$ and $m$ queries. For each query, given $l$ and $r$, you need to calculate the "nediam" $f([p_l, p_{l + 1}, \ldots, p_r])$.

To speed up the input process, we will use the following method. The first line contains six positive integers $n, m, seed, A, B, C$. The second line contains a permutation $p_1, p_2, \ldots, p_n$. For the next $m$ queries, you will generate the pair $(l, r)$ as follows: ```cpp unsigned seed, A, B, C; inline unsigned rnd() { seed = A * seed * seed + B * seed + C; seed = seed ^ (seed > 19); return seed; } inline std::pair gen() { int l, r; do { l = rnd() % n + 1; r = rnd() % n + 1; } while (abs(l - r) < 2); if (l > r) { std::swap(l, r); } return std::make_pair(l, r); } ``` For each query, call `gen()` once to generate the pair $(l, r)$ for that query.

To speed up the output process, we will use the following method. Let the answer for the $i$-th query be $ans_i$. You need to output $(1 \times ans_1) \oplus (2 \times ans_2) \oplus \cdots \oplus (m \times ans_m)$, where $\oplus$ denotes the bitwise XOR operation.

#### Sample $1$ Explanation The generated four queries are $(1, 4), (1, 3), (1, 3), (2, 4)$, with answers $2, 3, 3, 3$ respectively. Therefore, you need to output $(1 \times 2) \oplus (2 \times 3) \oplus (3 \times 3) \oplus (4 \times 3) = 2 \oplus 6 \oplus 9 \oplus 12 = 1$. For the first query, choosing the contiguous subsequence $[1, 3, 4]$ or $[3, 4, 2]$ will result in the deletion of $3$. After removing $3$, the remaining sequence is $[1, 4, 2]$, and the median is $2$. #### Subtasks and Constraints | Subtask ID | $n \le$ | $m \le$ | Special Properties | Score | | :-: | :-: | :-: | :-: | :-: | | $1$ | $18$ | $100$ | No | $9$ | | $2$ | $10^6$ | $5 \times 10^6$ | A | $5$ | | $3$ | $10^3$ | $10^4$ | No | $19$ | | $4$ | $10^5$ | $10^5$ | No | $17$ | | $5$ | $10^6$ | $10^6$ | B | $15$ | | $6$ | $10^6$ | $10^6$ | No | $13$ | | $7$ | $10^6$ | $5 \times 10^6$ | No | $22$ | - Special Property A: $p_i = i$. - Special Property B: $p$ is randomly generated with equal probability from all permutations of $1 \sim n$. For all tests, it is guaranteed that: - $3 \le n \le 10^6$; - $1 \le m \le 5 \times 10^6$; - $0 \le seed, A, B, C < 2^{32}$; - $p$ is a permutation of $1 \sim n$.