AGC002D

· · 题解

一个比较显然的思路是建出可持久化并查集同时维护 size，然后二分时间直接取出 size 判断即可。

但是发现这题每个版本只会衍生出一个新的版本，所以不用真的写个主席树去维护这个并查集。

考虑按秩合并，这种合并的方式发现每个点的 fa 数组只会有两个取值，一个是它自己，一个是它作为根被合并出去时的 fa，我们只需要顺便维护一下这个被合并的时间就行了。

考虑维护 size，发现每个时间只会更新一个根的 size，所以对每个点开个 vector 存下更新的时间和更新后的 size 即可。

每次询问外面有一层二分，并查集按秩合并和利用 vector 查询 size 都是 O(\log n) 的复杂度，所以总复杂度为 O(n\log^2n)。

具体实现见代码。

https://atcoder.jp/contests/agc002/submissions/33327714