【题解】CF1479D Odd Mineral Resource 随机化+主席树/莫队 — zhoukangyang

题面

CF1479D Odd Mineral Resource

给定一颗有 $n$ 个节点的树，每一个节点有一种颜色 $a_i$。$q$ 次询问，每次询问点 $x$ 到点 $y$ 的最短路径上是否有一种编号在 $[l, r]$ 的颜色，满足其出现次数为奇数。如果有，输出任意一个；否则输出 -1。

数据范围：$1 \le n, q \le 3 \times 10^5$，$1 \le l \le r \le n$，$1 \le a_i, x, y \le n$。

题解

介绍两种方法。

法 1

这是一个有关树上数颜色的问题，用树上莫队。

对颜色编号进行分块，块内维护可能成为答案的颜色。

修改时，如果此颜色的出现次数是奇数，那么就认为这种颜色可能成为答案。

查询的时候，对于整块扫描可能成为答案的颜色。对于一个扫到的数 $x$，如果出现次数确实是奇数就停，否则就把 $x$ 从可能成为答案的数中删除。散块暴力即可。

时间复杂度 $\Theta(n \sqrt m)$

喜提最劣解。

aclink

法 2

出现奇数次可以用异或来处理。

如果对于每一个元素，进行随机赋值。我们查询树上 $u$ 到 $v$ 上，编号在 $l$ 到 $r$ 的权值异或和，如果是 $0$ 那么我们就认为答案是 -1。

然后我们进行二分答案，查询一下 $[l, mid]$，如果异或和不是 $0$ 就在 $[l, mid]$ 往下做，否则 $[mid + 1, r]$ 的异或和一定不是 $0$，在 $[mid + 1, r]$ 往下做。

这个可以主席树维护。由于主席树的优良性质，我们可以直接在主席树上二分。时间复杂度 $\Theta((n + m) \log n)$

喜提最优解。

aclink