题面

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

分类: 文章

zhoukangyang

orz Qiuls! [cnblogs](https://www.cnblogs.com/zkyJuruo/) 怎么上传头像啊qaq

1 条评论

Qiuly · 2021年2月18日 3:59 下午

/se 现在您已经获得了” 作者” 权限!
这意味着以后写文章不用等审核就可以直接通过了 qwqwq

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注