题解

· · 个人记录

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

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

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

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

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

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

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

哈希。

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

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

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

如提示中所言。

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

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

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

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

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

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

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

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