Petrozavodsk Summer 2019. Day 5 选做

https://qoj.ac/contest/1510

最大流转最小割，等价于删除最小个数的点使得第 $i$ 列与第 $j$ 列不连通。

固定其中一者 $i$，扫描线 $j$，记录当前可达点集 $S$，dp 状态为 $f_{S,j}$。每次转移结束后下传删第 $j+1$ 层点的贡献，得到一个对于单个 $i$ 复杂度 $\mathcal O(n2^kk)$ 的做法。拓展到求所有 $(i,j)$ 的和，依然扫描线 $j$。类似于扫描线加入左端点的手法，对于一个 $f$ 记录所有点的信息，而 $f_S$ 值域很小，这样状态就是 $f_{S,j,v}$ 表示扫到 $j$ 有多少个 $i$ 的 $dp_{S,j}=v$。时间复杂度 $\mathcal O(n2^kk^2)$。

从任意一个点向更大的走过去一直走可以走到最大值，但是路径长度是 $n^2$ 级别的。用一个类似于二分的手法来定位，也就是网格图分治。取一个靠中间的分界列。

第一次递归时，把这一列都问一遍，求出这一列的最大值 $v$ 以及它左右侧三个位置的最大值 $l,r$。如果 $v>\max(l,r)$ 那么 $v$ 就是 global max；若 $l<v<r$，那么最大值在右侧，否则右侧的路径无法来到左边，$l>v>r$ 同理。不会出现 $l>v<r$。

后续递归时就存在边界值了，在上述的基础上考虑询问过的最大值在哪一侧即可。不然不可能走到另一侧。询问次数不超过 $3n+12\log n$。

固定排列集求方案数，考虑容斥。钦定一个颜色集合，要求其出现位置两两偏序，这样分成的若干层内部是一个多重集组合数相乘。长度较小时直接考虑这张偏序关系图，长度较大时这个图的边数很少，并且边权是固定的所以容易做到与边数同阶的递推。总边数期望是 $\sum_{l}2^{-l}n^2(k-l+1)=\mathcal O(n^2k)$，时间复杂度 $\mathcal O(nk^2+n^2k)$。

设计 dp 状态 $f_u$ 表示 $u\to n$ 的最优期望时间。边之间成功率最开始都是 $\frac{3}{4}$，考虑对于后继按照 $f$ 进行排序。第一条边成功率是 $\frac{3}{4}$，剩下 $\frac{1}{4}$ 的概率变成 $\frac{1}{2}$。继续做，发现策略形如尝试一个前缀之后再一直尝试一个单点。

问题是这样需要求出 $\{f\}$，初始只有 $f_n=0$ 已知。显然与 $n$ 相邻的点的 $f$ 都可以求，进一步地，考虑 dijkstra 算法，每次取出 $\min f$，然后对邻边进行松弛。其前缀序列就是自动有序的，相当于枚举了在哪里结束一直试这个单点。维护当前情况的代价，时间复杂度 $\mathcal O(n\log n)$。

枚举不使用哪个点，求出剩余点的邻域交集大小。求和后减去 $k-1$ 倍全体邻域交集大小就是答案。考虑树上邻域取交的结果怎么刻画，发现就是某条边或者某个点的邻域（树上圆理论）。对于每条边中间插入一个虚点，这样就全在点上了。合并即取出树上路径讨论中点即可。前后缀处理信息，这样就不用撤销了。预处理 $\text{lca}$ 可以做到 $\mathcal O(1)$ 合并。最终要求某个点的邻域大小，可以直接上点分树求一下。时间复杂度 $\mathcal O((n+\sum k)\log n)$。

动态支持 fail 树上挂叶子，以及查询某个点的子树大小。离线的话造一个重链剖分是容易的，在线可以直接平衡树维护括号序，或者直接套用 border 的性质：一个串的 border 可以划分为 $\log n$ 段等差数列，就实现了重剖的功能。每条链维护支持最后插入的 BIT。时间复杂度 $\mathcal O(n\log^2n)$。