目录
错题集 2
1、Ancient Distance
题意
给一个有根树，在树上选择 $k$ 个关键点(根必须选)，使得所有点到最近关键祖先(可以是自己)距离的最大值最小。
求出 $k$ 分别为 $1\sim n$ 时答案的和。
题解
考虑贪心，假设已知最小距离为 $d$，发现每次取树中深度最大的点的 $d$ 级祖先作为关键点最佳。
而选取该节点作为关键点后可以直接删去该关键点的子树，然后继续从新的树中选择深度最大的点。
考虑用树链剖分和线段树维护每个点的 $d$ 级祖先和子树删除操作。
另一方面，发现如果将最小距离设为 $d$，则每次子树删除操作至少删去 $d$ 的节点，于是操作次数为 $O(\frac nd)$。
考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。
总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$。
于是总时间复杂度为 $O\left(n\log^2 n\right)$。
注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。
2、Greetings Souvenir
题意
给定一棵大小为n的树，且树上的每个节点有一个权值 $a_i$，现在要给每个节点确定一个数值 $b_i$。
定义 $val_i=b_i\ast$( $i$ 子树内有多少个点的权值 $a_i$ 等于 $b_i$)，要求所有点 $val_i$ 的 $mex$ 尽可能大。
题解
乱搞题，首先考虑每个 $a$，假如有 $c_i$ 个节点权值为 $a$，对所有 $b_i=a$ 的点，其 $val_i$ 的可能取值只有 $a,2a\cdots c_ia$ 共 $c_i$ 个。
于是所有可能的取值只有 $\sum_{i=1}^n c_i=n$ 个。
在每个点 $i$ 与其可能取值的 $val_i$ 间连一条边，时空间复杂度 $O(n^2)$。为防止爆空间，本题用 $\text{bitset}$ 存边。
最后考虑进行二分图匹配，从小到大给所有可能值匹配，如果匹配失败则立即结束，时间复杂度 $O(n^3)$。
考虑乱搞，强行对匈牙利算法使用当前弧优化，于是时间复杂度降为 $O(n^2)$。
3、Interval
题意
给定序列 $a_1,a_2\cdots a_n$，定义函数 $F(l,r)=a_l\text{&} a_{l+1}\text{&} \cdots a_r$，定义不可重集 $S(l,r)=\{l\le a\le b\le r,F(a,b)\}$。
接下来若干询问，每次询问 $|S(l,r)|$，强制在线。
题解 1
首先，对固定的 $r$，易知 $F(l,r)$ 至多有 $O(\log v)$ 个取值，因为 $F(l,r)-F(l-1,r)=0$ 或 $F(l,r)$ 中的某个不为 $0$ 的位。
线段树可以 $O(\log n)$ 快速计算 $F(l,r)$。考虑对 $l$ 二分，可以 $O(\log n\log v)$ 得到对固定的 $r$，$F(l,r)$ 的所有可能取值。
接下来考虑维护答案，发现 $S(l,r-1),S(l,r)$ 具有高度相似性，于是考虑使用可持久化线段树维护。
线段树的每个版本 $r$ 维护所有 $S(l,r)(1\le l\le r)$ 的答案，而版本 $r$ 只需要在版本 $r-1$ 的基础上稍微修改即可。
线段树相邻版本的差异来自 $F(l,r)(1\le l\le r)$，$F(l,r)(1\le l\le r)$ 至多有 $O(\log v)$ 个取值，考虑依次插入线段树。
而又有 $S(l,r)\subset S(l-1,r)$，于是考虑差分维护 $|S(l,r)|(1\le l\le r)$，令 $|S(l,r)|=\sum_{i=l}^r d_{i,r}$。
对所有具有相同的值 $v$ 的 $F(a,b)(b\le r)$，设 $\text{last}=\max(a)$，于是有 $1 \le l\le \text{last},v\in S(l,r)$。
于是对所有不同的值，考虑维护每个值对 $d_{\text{last},r}$ 的贡献即可，时空间复杂度 $O(n\log n\log v)$。
题解 2
对固定的 $r$，考虑枚举过程中维护 $a_1\sim a_{r-1}$ 中数位为 $0$ 的最后位置 $a_\text{last}$。
如果 $a_r$ 某数位为 $0$，则该数位对应的 $\text{last}$ 必有 $F(\text{last}+1,r)\neq F(\text{last},r)$。
于是可以 $O(\log v)$ 时间求出所有 $F(l,r)(1\le l\le r)$ 的可能取值。
而对于可持久化线段树的维护，可以改用区间标记永久化维护 $F$ 带来的影响。
4、African sort
题意
给定排列 $p$，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价。
要求将 $p$ 转化为 $1,2\cdots n$，求最优策略下最小代价的期望。
题解
将 $p$ 转化为 $1,2\cdots n$ 等价于该置换只存在长度为 $1$ 的循环。
有引理 $1$：随机打乱一个长度为 $n$ 的循环，则循环的每个元素将等概率出现在长度为 $1\sim n$ 的循环中。
引理 $2$：每次选择一个完整的循环将其全部打乱一定是最佳选择。
设将一个长度为 $n$ 的循环打乱成 $n$ 长度为 $1$ 的循环的最小期望代价为 $f(n)$。
单独考虑每个点的期望代价，每个点在循环长度为 $i$ 的代价由 $i$ 个点均摊。
最后总代价为单个点代价的 $n$ 倍，得到$f(n)=n\sum_{i=1}^n \frac{\frac {f(i)}{i}}n+n=\sum_{i=1}^n\frac {f(i)}i+n(n\gt 1)$。
转化，得到 $f(n)=\frac {n(f(n-1)+1)}{n-1}(n\gt 2)$，边界条件 $f(2)=4,f(1)=0$。
5、Hacker Cups and Balls
题意
给定一个 $1\sim n$ 的排列，一共 $m$ 个操作。
每个操作为选择一个区间，将其按升序或降序排序。
问经过所有操作后排列中间的数为多少，保证 $n$ 为奇数。
题解
于是考虑二分答案 $v$，答案的意义是验证中间的数是否不超过 $v$，显然这样的结果具有单调性。
对序列中的数，如果该数大于 $v$，则置为 $1$，否则置为 $0$。
于是区间排序操作可以使用线段树处理，最后查询中间的数的数值是否为 $0$ 即可，时间复杂度 $O(n\log^2 n)$。
6、Zero Game
题意
给定一个长度为 $n$ 的 $01$ 串，$q$ 个询问。
每次询问允许进行 $k_i$ 次操作，每次操作可以任意移动一个字符，问 $k_i$ 次操作后的最长的连续 $0$ 串的长度。
题解
考虑贪心，不难发现最佳答案一定为选择一段区间，移除区间的所有 $1$，如果还有剩余的操作此数，则将区间外的 $0$ 移入区间。
记 $\text{pre}_i$ 表示前 $i$ 个字母中有多少个 $1$，$a_i=i-2\text{pre}_i$。
对一个合法的区间 $[l,r]$，区间中原有 $0$ 的个数为 $r-l+1-(\text{pre}_r-\text{pre}_{l-1})$，可以额外移入的 $0$ 的个数为 $k-(\text{pre}_r-\text{pre}_{l-1})$。
于是该区间的答案为 $r-l+1-(\text{pre}_r-\text{pre}_{l-1})+k-(\text{pre}_r-\text{pre}_{l-1})=k+(r-\text{pre}_r)-(l-1-\text{pre}_{l-1})=k+a_r-a_{l-1}$。
考虑对每个右端点 $r$，寻找满足 $\text{pre}_r-\text{pre}_i\le k$ 的最小的 $i$。
由于 $\text{pre}_{i}$ 递增，于是可以用单调队列维护维护递增的 $a_i$ 序列。对每个右端点，枚举后加入队列即可。
时间复杂度 $O(nq)$。
7、Enigmatic Partition
题意
定义 $f(n)$ 等于满足下列条件的排列数：
- $a_1+a_2+\cdots a_k=n$
- $a_{i+1}-1\le a_i\le a_{i+1}$
- $a_k=a_1+2$
求 $\sum_{i=l}^rf(i)$。
题解一
考虑枚举 $a_1$，当 $a_1\lt k$ 时，考虑 $\text{dp}$。$\text{dp}(s,i,pos)$ 表示当前和为 $s$，同时 $a_1=i$，并且已经选择了 $i\sim i+pos$ 的数的方案数。
$\text{dp}$ 状态数为 $3nm$，于是时间复杂度为 $O(nm)$。
当 $a_1\le k$ 时，记 $a_1=\text{lef},a_1+1=\text{mid},a_1+2=\text{rig}$，$\text{lef}$ 的个数为 $l$，$\text{mid}$ 的个数为 $m$，$\text{rig}$ 的个数为 $r$。
于是考虑先将 $\text{lef},\text{rig}$ 合并为 $\text{mid}$，然后如果 $l\gt r$，则枚举 $l$ 与 $m$，然后再考虑拆分 $m$ 的方案，有 $\lfloor\frac {m-1}2\rfloor$ 种。
同样如果 $l\le r$，则枚举 $r$ 与 $m$，然后再考虑拆分 $m$ 的方案，有 $\lfloor\frac {m-1}2\rfloor$ 种。
时间复杂度 $O\left(\sum_{i=m}^n (\frac ni)^2\right)$，可以近似为 $O\left(\frac {n^2}m\right)$。
于是总时间复杂度 $O\left(nm+\frac {n^2}m\right)$。取 $m=O(\sqrt n)$，时间复杂度为 $O(n\sqrt n)$。
题解二
考虑差分维护，观察 $a_1=1,k=7$ 的表格。
| n | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 5个3 | 1233333 | |||||||||||
| 4个3 | 1123333 | 1223333 | ||||||||||
| 3个3 | 1112333 | 1122333 | 1222333 | |||||||||
| 2个3 | 1111233 | 1112233 | 1122233 | 1222233 | ||||||||
| 1个3 | 1111123 | 1111223 | 1112223 | 1122223 | 1222223 | |||||||
| num | 1 | 1 | 2 | 2 | 3 | 2 | 2 | 1 | 1 | 0 | 0 | 0 |
| 一阶差分 | 1 | 0 | 1 | 0 | 1 | -1 | 0 | -1 | 0 | -1 | 0 | 0 |
| 二阶隔项差分 | 1 | 0 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | 1 |
| 对应位置 | $a_1k+3$ | 0 | 0 | 0 | 0 | $(a_1+1)k+1$ | $(a_1+1)k+2$ | 0 | 0 | 0 | 0 | $(a_1+2)k$ |
于是考虑枚举 $a_1,k$ 即可，时间复杂度 $O(n\log n)$。
