CF1805E There Should Be a Lot of Maximums

Pengzt · 2023-04-17 13:30:50 · 题解

CF1805E

看到维护树上问题，可以想到线段树合并。

但直接维护显然不行，要一点技巧。

发现 val 的出现次数 cnt_{val} 如果 \ge 3，那么一定是一个候选项，若 cnt_{val} = 1，那么一定不能作为候选项。

于是可以用权值线段树维护对于 val 有 cnt_{val} = 2 的 val。先离散化，然后再合并线段树。查找时，若右子节点的 \max = 2 或右子节点的 \min = 0，就递归查找右节点，反之亦然。若左右子节点都不满足，就返回 0，实现需要一点细节。

空间只需要开 32 倍。

时间复杂度：\mathcal{O}(n\log n)。

评测记录

最后提供一组 hack：

输入：

10 
1 2
1 3
1 4
1 5
1 6
2 7
2 8
3 9
4 10
1 3 3 3 3 4 10 4 6 2

输出：

3
4
4
4
3
4
3
4
4