题目大意
给定一棵 $n$ 个点的 AVL 树（点权恰好为 $1$ 到 $n$），你需要选择其中的 $k$ 个点，满足：
- 如果要选一个点，那么它的祖先也必须选。也就是选出来的 $k$ 个点会组成一棵新的树。
- 这棵新的树也必须是 AVL 树。
（放个传送门里面有图片可以看看例子
每种选法可以表示为一个长度为 $n$ 的 01 串（表示每个点选或不选），你需要求出字典序最大的方案。
$1 \leq k \leq n \leq 5 \times 10^5$
4s，256MB
题解
做这种全服个位数通过的题其实挺有快感的
首先大的框架肯定是贪心，从小到大 check 每个点能不能选。
check 的依据就是两点：会不会跟已选的点冲突，会不会必需结点数目超过 $k$ 的限制。AVL 树的一个性质是，树高是 $O(\log n)$ 的。基于这个我们可以设计出一个粗略的 check 的方法：
（$lson,rson$ 表示一个结点的左右儿子）
设要 check $s$ 这个点，从 $s$ 开始不断往父亲跳，维护当前子树最少要选的点数 $nownum$，以及所选的层数 $nowdeep$。假设当前点是 $x$，父亲为 $y$。
若 $x$ 是 $y$ 的右儿子，则 $y$ 的左儿子肯定已经全部考虑过了，定死了不能变了，所以只需判断这俩兄弟的层数差是否在 $1$ 以内即可，然后更新 $nowdeep$ 和 $nownum$；
若 $x$ 是 $y$ 的左儿子，则 $y$ 的右儿子肯定全都没考虑，我们预处理一个 dp 数组 $f_{i,j}$ 表示以 $i$ 为根的子树选 $j$ 层的最少花费，那么这时只需要使 $nownum$ 加上 $f_{rson_y,nowdeep-1}$ 即可。
最后判断 $nownum \leq k$ 即是合法。
会有一些问题：当 $x$ 是 $y$ 左儿子时，$y$ 的右儿子可能曾经被 $x$ 子树里的其他结点提出过更大的层数要求，记为 $tag_{rson_y}$，是的这其实就是一个不断打 tag 的过程，所以实际上右儿子要选的层数应该是 $f_{rson_y,\max\{nowdeep-1,tag_{rson_y}\}}$。
然后，当 check 一个点成功时，它必须沿着祖先链上去给所有右兄弟更新 tag。
这时又会有新的问题：当前结点 $x$ 本身可能会有一个 $tag_x$ 的任务，然而我们为了使点数最少我们一直都只选必需的点，这导致 $nowdeep$ 可能完不成 $tag_x$ 这个任务，我们就需要计算现在 $nowdeep$ 层补到 $tag_x$ 层需要额外付出多少代价。
记 $h_i (i \ge nowdeep)$ 表示当前子树从选 $nowdeep$ 层追加到选 $i$ 层需要额外补多少代价。这个东西也很好维护，当 $nowdeep$ 变大成 $nowdeep’$ 时，所有的 $h_i-=h_{nowdeep’}$；当往上跳遇到右兄弟时，再维护 $h_i=\min\{h_{i-1}+f_{rson,i}-f_{rson,t},~h_i+f_{rson,i-1}-f_{rson,t}\}$。（其中 $t=\max\{nowdeep-1,tag_{rson}\}$，因为我们维护的是额外补的差价，而 $f_{rson,t}$ 是已经付出的）
时间复杂度：每个点往上跳是 $O(\log n)$ 步的，每跳一次维护一下 $h$ 数组又是 $O(\log n)$ 的，因此总的是 $O(n \log^2 n)$。但它跑得飞快，甚至这题其他人写的像是 $O(n \log n)$ 的（我都没看懂）用时是我的若干倍。。
（另外有些小技巧，比如如果一个点它的(左)子树中有人确定要选了，那么它作为祖先就一定要选，就不用 check 了，这样的话任何要 check 的点都必然是左子树不选的，于是各变量的初值也方便多了。。
代码
1 |
|