快速中位数变换 - Problem

长度为 $k$ 的数组的中位数是指将元素按非降序排列后，位于 $\lfloor \frac{k+1}{2} \rfloor$ 位置的元素。例如，$[5, 1, 2, 3]$ 的中位数是 $2$，$[2, 1, 1]$ 的中位数是 $1$。

Little Cyan Fish 给了你一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$。数组下标从 $0$ 开始。

对于一个整数 $X_0$，我们定义 $(a, b, X_0)$ 的“快速中位数变换”（称为 $\text{FMT}(a, b, X_0)$）：

令 $X$ 为一个变量，初始时 $X = X_0$。
对于每个从 $0$ 到 $nm - 1$ 的整数 $i$，依次执行以下操作：
- 计算数组 $[a_{i \bmod n}, b_{i \bmod m}, X]$ 的中位数。令该中位数为 $Y$。
- 将 $Y$ 赋值给 $X$。
我们定义 $\text{FMT}(a, b, X_0)$ 为过程结束时 $X$ 的值。

你将收到 $q$ 次询问。每次询问包含三个整数 $x, y', X'_0$。对于每次询问，执行以下操作：

将 $a_x$ 更新为 $y' \oplus lastans$，其中 $\oplus$ 表示按位异或运算，$lastans$ 是上一次询问的结果（初始为 $0$）。
计算并输出 $\text{FMT}(a, b, X'_0 \oplus lastans)$。

注意：询问不是独立的；它们按顺序发生，且每次询问的影响会持续存在。

第一行包含三个整数 $n, m, q$ ($1 \le n, m, q \le 3 \times 10^5$)，分别表示 $a$ 的长度、$b$ 的长度以及询问次数。

第二行包含 $n$ 个非负整数 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < 2^{29}$)。

第三行包含 $m$ 个非负整数 $b_0, b_1, \dots, b_{m-1}$ ($0 \le b_i < 2^{29}$)。

接下来 $q$ 行。第 $i$ 行包含三个非负整数 $x, y', X'_0$ ($0 \le x < n, 0 \le y', X'_0 < 2^{29}$)，表示第 $i$ 次询问。

输出 $q$ 行。第 $i$ 行包含一个整数，表示第 $i$ 次询问的答案 $\text{FMT}(a, b, X'_0 \oplus lastans)$。

QOJ.ac