AT_abc202_e [ABC202E] Count Descendants 题解

_32_qwq · 2023-12-30 09:11:13 · 题解

首先用 dfn 序转化为区间问题，然后用线段树维护即可。

怎么维护呢？首先你可以发现，因为线段树深度 O(\log n)，所以所有节点维护的区间大小加起来就是 O(n\log n)。

那么我们给线段树每个节点用个 map 维护以下内部每种深度有几个即可。

但是 map 似乎会被卡，发现 [1,n] 域很小，换成 unorderd_map 似乎没问题。

时间 O(n\log n)，空间 O(n\log n)。