[Ynoi2013] Ynoi

· · 题解

Description

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

限制

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]，其中

把数组 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) 分裂。

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

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)).