自动搬运

查看原文

来自洛谷，原作者为

	ftiasch 这个学院最强大的女孩子的朋友

搬运于2025-08-24 22:12:33，当前版本为作者最后更新于2021-03-08 10:18:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

维护一个数组 $a[n]$，支持 $q$ 次下面 $3$ 种操作：

• $\mathrm{update}(l, r, x)$: 对于 $i \in [l, r]$, 把 $a[i]$ 设为 $(a[i] \oplus x)$;
• $\mathrm{sort}(l, r)$: 把 $a[l..r]$ 排序；
• $\mathrm{sum}(l, r, x)$: 返回 $a[l] \oplus \dots \oplus a[r]$.

限制

$1 \leq n, q \leq 10^5$

$0 \leq a_i, x < 10^8$

Solution

对于集合 $S$ 和数字 $x$, 用 $\mathrm{sort}(S) \oplus x$ 代表序列 $[s_1 \oplus x, \dots, s_m \oplus x]$，其中

• $S = \{s_1, s_2, \dots, s_m\}$,
• $s_1 \leq \dots \leq s_m$.

把数组 $a[n]$ 划分成若干对子 $(S_1, x_1), (S_2, x_2), \dots$ 使得

$$a = (\mathrm{sort}(S_1) \oplus x_1) + (\mathrm{sort}(S_2) \oplus x_2) + \dots $$

---

对于区间 $[l, r]$ 的操作，假设存在 $i \leq j$ 满足

$$a[l..r] = (\mathrm{sort}(S_i) \oplus x_i) + \dots + (\mathrm{sort}(S_j) \oplus x_j). $$

否则，需要把至多 $2$ 对 $(S, x)$ 分裂。

• $\mathrm{update}$ 操作，更新$x_i, \dots, x_j$；

• $\mathrm{sort}$ 操作时，把这些对子合并为 $\mathrm{sort}((S_i \oplus x_i) \cup \dots \cup (S_j \oplus x_j))$.

• $\mathrm{sum}$ 操作时，查询 $\bigoplus_{k = i}^j \mathrm{sum}(S_k) \oplus x_k$.

---

因此，集合 $S$ 需要支持 $4$ 种操作：

• $\mathrm{partition}(S, k) = (S', S'')$ where $\max S' \leq \min S''$ and $|S'| = k$,
• $\mathrm{flip}(S, y) = \{x \oplus y : x \in S\}$,
• $\mathrm{merge}(S, S') = S \cup S'$,
• $\mathrm{sum}(S) = \bigoplus_{x \in S} x$.

Trie 支持这 $4$ 个操作。为了节省空间，可以使用 Compacted Trie.

注意 $10^8 < 2^{27}$, $27 < 2^5$, 所以一个 uint32_t 同时可以存下标记和长度。

---

全局使用一个线段树处理区间操作，把 $(S_i, x_i)$ 存储在 $|S_1| + \dots + |S_{i - 1}|$.

区间操作前，找到 $< l$ (and $\leq r$) 的最后一个 $(S_i, x_i)$，处理可能的分裂。

复杂度是 $O((q + n) (\log n + \max \log a_i))$.