0123 训练小记
BZOJ 2159 Crash 的文明世界
把 \(k\) 次方用第二类斯特林数拆开，然后换根 dp 统计即可。
时间复杂度：\(O(nk)\)。
CF453E Little Pony and Lord Tirek
每次操作会推平一个区间，所以考虑颜色段均摊。
考虑询问的时候暴力查每一段。
这一段要么是只有一个元素，还没动过，这种情况直接暴力，总共 \(O(n)\) 次。
还有一种情况是动过，从某个时刻 \(t\) 开始从 \(0\) 开始长。
那么发现同一段的生长时间相同，按照 \(\lceil\frac {m_i} {s_i}\rceil\) 升序排序后是前一段满了，后一段没满。
就可以用主席树维护。
把所有主席树的询问离线下来用 \(\text{BIT}\) 可以做到更优秀的常数。
时间复杂度：\(O((n+q)\log n)\)。
UOJ55 紫荆花之恋
调了一下午破防了。
萌新的第一道点分树就做这个/fn/fn
首先考虑不强制在线怎么做。
先把点分树建好。
加进来一个点之后枚举在点分树上的 \(\text{LCA}\)，即原树上的分治中心。
类比 \(dis(i,j)=dep(i)+dep(j)-2dep(\text{LCA})\)，把 \(dis(i,j)\) 写成：
\[dis(i,j)=dis(i,u)+dis(u,j) \]\(u\) 是分治中心，注意点分树的题不要把 \(\text{LCA}\) 算距离的方式和这个搞混了。
然后就要满足 \(dis(i,u)+dis(u,j)\le r_i+r_j\)。
移项之后得到 \(dis(i,u)-r_i\le dis(u,j)+r_j\)。
每个点开一棵平衡树，把右边的式子放进 \(u\) 的平衡树中。
然后新加入 \(i\) 的时候平衡树查 \(rk\) 即可，再把 \(i\) 加进所有平衡树里。
由于点分树满足所有点子树大小之和为 \(O(n\log n)\)，所以这个做法总共是 \(O(n\log^2n)\) 的。
但是这个题强制在线。
这个时候就有一个常见套路：根号重构。
把时间分块，每隔 \(B\) 重构一次，这样每次会有 \(O(\frac n B)\) 个点不在点分树内。
暴力查询，距离用倍增 \(\text{LCA}\) 算。
取 \(B=\sqrt n\)，可以得到一个 \(O(n\sqrt n \log^2n)\) 的垃圾复杂度做法。
发现重构很慢，查询散点很快，平衡一下。
直接取 \(B=\sqrt{\frac n{\log n}}\)，可以变成 \(O(n\sqrt{n\log n}\log n)\)。
继续考虑优化，重构点分树两个 \(\log\) 没法优化，那么取 \(B=\frac {\sqrt n}{\log n}\)。
重构的部分是 \(O(n\sqrt n \log n)\)。
对于散点查询，散点个数现在是 \(O(\sqrt n\log n)\)，得优化到 \(O(1)\) 求一个。
对于每个散点维护祖先中深度最深的在点分树中的点，记作 \(nr_i\)。
下文令 \(j<i\)，即每次加入 \(i\)。
询问 \((i,j)\) 的时候，如果 \(nr_i\ne nr_j\)，那么在原树中的 \(\text{LCA}\) 就一定在点分树中，为 \(nr_i\) 和 \(nr_j\) 的 \(\text{LCA}\)。
每次重构点分树的时候维护 \(ST\) 表来支持 \(O(1)\) 的 \(\text{LCA}\)。
对于 \(nr_i=nr_j\)，会有两种情况，一种是 \(\text{LCA}\) 为 \(nr_i\)，一种不是。
对于不是的，那么 \(\text{LCA}\) 一定是散点，而且在 \(nr_i\) 的包含 \(i\) 的子树内。
那么找到这个子树的根（暴力跳父亲），跑一次 \(dfs\) 即可统计出来。
跳父亲是散点个数级别的，\(dfs\) 也是。
剩下的没被统计的散点，\(\text{LCA}\) 都是 \(nr_i\)。
所以就变成了 \(O(n\sqrt n\log n)\)。
然后发现平衡树太慢了跑不过去。
这个时候发现点分树是静态的，不需要维护平衡树，在 vector 排序后二分即可。
ARC153F Tri-Colored Paths
这个题第二天也发了，这里不写了（
标签：0123,log,训练,text,sqrt,LCA,nr,dis,小记 From： https://www.cnblogs.com/hellojim/p/17066366.html