本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-08 22:33:12

我们应该怎么维护这些集合？

如果简单的维护每个集合包含哪些数，能快速询问对称差吗？好像很难。

可不可以，考虑在值域上维护？

在值域上维护，用什么数据结构呢？维护什么信息呢？

我们设 $q_{ij}$ 表示第 $i$ 个集合中 $j$ 是否存在，为 $0$ 或 $1$。

那么，$w$ 不在 $x$ 与 $y$ 集合的对称差中，当且仅当 $q_{xw} = q_{yw}$。

相等。想起来什么东西了吗？

哈希。

发现，我们并不需要知道对称差中全部的元素。

因为我们只需要知道最大的，同时，我们又在值域上操作，所以……

想到用什么数据结构了吗？

如提示中所言。

我们用一颗值域线段树来维护一个集合，并在线段树上维护区间的哈希值。

操作一：加入一个数。也就是线段树单点修改某点为一。

操作二：查询对称差的最大值。

我们并不需要知道对称差里头的所有数。

我们想知道的是最大的 $w$，满足 $q_{xw} \ne q_{yw}$。

由于我们维护了区间的哈希值，那么这个问题可以用线段树二分解决。

只需要在每个节点，判断两棵树的右儿子是否相等。相等就往左儿子走，否则往右儿子走，直到走到叶子。

于是本题做完了。时空复杂度都是 $O(n\log V)$。