P11955「ZHQOI R1」覆盖 题解

· · 题解

当 n=2^k 时，考虑树形 dp，需要合并左子树和右子树的答案，可以将左子树右链和右子树左链上的点错位相配对，配对的结点都可以用同一个集合覆盖。有 f(2^k)=2f(2^{k-1})-k+1 。在两侧待合并链的长度不同时，可以合并的点数即两侧点数较小值，所以 f(n)=f(\left \lfloor \frac{n}{2} \right \rfloor)+f(\left \lceil \frac{n}{2} \right \rceil)-\left \lfloor \log_{2}{\left \lceil \frac{n}{2} \right \rceil } \right \rfloor (n\ge4)，记忆化搜索即可解决单点问题。

结论：f_{1...n} 可以被划分为 \mathcal{O}(\log n) 段 d=1 的等差数列和 \mathcal{O}(\log n) 个值相同的连续段。

考虑在一棵满二叉树上按照顺序依次向下挂一对儿子，根据之前的分析，容易得出在这个过程的前半，答案每次加一，后半答案保持不变，而满二叉树的深度是 \mathcal{O}(\log n) 级别的，所以结论是正确的。

预处理出每段和，段间前缀和，可以 \mathcal{O}(1) 找到一个值所属的段，总复杂度 \mathcal{O}(q+\log n)。