P11283 「GFOI Round 2」Turtle and Nediam

对一个元素互不相同的长度 $\ge 3$ 的正整数序列 $a$，定义 $a$ 的“肿胃数（nediam）”$f(a)$ 为： - 当 $|a| = 3$ 时，$f(a)$ 为 $a$ 的中位数； - 当 $|a| > 3$ 时，取 $a$ 的任意一个长度为 $3$ 的子段 $[a_i, a_{i + 1}, a_{i + 2}]$，记这个子段的中位数为 $x$，$a$ 删掉 $x$ 后的序列为 $b$，$f(a)$ 为所有 $b$ 中 $f(b)$ 的最大值。 乌龟给你一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$ 和 $m$ 次询问，每次询问给定 $l, r$，你需要求出 $[p_l, p_{l + 1}, \ldots, p_r]$ 的“肿胃数（nediam）”，即 $f([p_l, p_{l + 1}, \ldots, p_r])$。

为了加快读入速度，我们采用以下读入方法。 第一行包含六个正整数 $n, m, seed, A, B, C$。 第二行包含一个排列 $p_1, p_2, \ldots, p_n$。 接下来的 $m$ 组询问，每组询问你要按照如下的方式生成 $(l, r)$： ```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); } ``` 每组询问调用一次 `gen()` 生成这组询问的 $(l, r)$。

为了加快输出速度，我们采用以下输出方法。 设第 $i$ 组询问的答案为 $ans_i$，你需要输出 $(1 \times ans_1) \oplus (2 \times ans_2) \oplus \cdots \oplus (m \times ans_m)$，其中 $\oplus$ 为按位异或。

#### 【样例解释 #1】 生成的四组询问分别为 $(1, 4), (1, 3), (1, 3), (2, 4)$，答案分别为 $2, 3, 3, 3$，所以你需要输出 $(1 \times 2) \oplus (2 \times 3) \oplus (3 \times 3) \oplus (4 \times 3) = 2 \oplus 6 \oplus 9 \oplus 12 = 1$。 对于第一组询问，选择子段 $[1, 3, 4]$ 或 $[3, 4, 2]$ 都会使得 $3$ 被删除。删除 $3$ 后的序列为 $[1, 4, 2]$，中位数为 $2$。 #### 【数据范围】 **本题使用捆绑测试。** | 子任务编号 | $n \le$ | $m \le$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $18$ | $100$ | 无 | $9$ | | $2$ | $10^6$ | $5 \times 10^6$ | A | $5$ | | $3$ | $10^3$ | $10^4$ | 无 | $19$ | | $4$ | $10^5$ | $10^5$ | 无 | $17$ | | $5$ | $10^6$ | $10^6$ | B | $15$ | | $6$ | $10^6$ | $10^6$ | 无 | $13$ | | $7$ | $10^6$ | $5 \times 10^6$ | 无 | $22$ | - 特殊性质 A：$p_i = i$； - 特殊性质 B：$p$ 从所有 $1 \sim n$ 的排列中等概率随机生成。 对于所有数据，满足： - $3 \le n \le 10^6$； - $1 \le m \le 5 \times 10^6$； - $0 \le seed, A, B, C < 2^{32}$； - $p$ 是一个 $1 \sim n$ 的排列。