2024.7.1 之后的做题小记

7.1 P7124 [Ynoi2008] stcm

维护一个 \(O(n\log n)\) 级别的子树补不删除莫队。

Solution 1：

考虑菊花图，忽略根节点，一个显然的做法是把这些节点扔进线段树，然后遍历某个节点时候就把它的兄弟节点内所有点加进来。

这个做法是线段树所有节点大小和即 \(O(n\log n)\)。

然后在一条链上做法简单，直接冲下去即可。

现在集合两种做法，重链直接冲，轻子树想办法用线段树合并一下。

不过考虑每颗子树大小不一样，直接建线段树，复杂度假假假。

改用合并果子式合并法建树，这叫 哈夫曼树（Huffman Tree），子树和小于 \(O(n\log n)\)，复杂度真真真。

然后重链权值视为 \(1\)，再拼接一下，就好了。

不过不好写，我是不想写的。

Solution 2：

想象拍平树，现在变成了序列上中间缺一节的不删除莫队。

看起来更困难，但是树上区间有一重要性质：任意两区间要么不交要么包含。

基于此得到一个分治做法：

\([l,r]\) 解决所有抠掉区间被它包含的询问。

只考虑包含 mid 的询问，不包含的直接递归处理。

然后你发现，所有包含 mid 的询问，由于上面那个性质，两个端点移动是单调的！

直接暴力移动即可，每轮 \(O(n)\)，总共 \(O(n\log n)\)，非常好写！！！