P11065
考虑如果一个点作为补给站可以覆盖到另一个点，那么将这两个点连边，题目就转化为两点之间路径的最小值最大是多少，不难使用 kruskal 重构树解决。考虑如何优化建边，显然一个点能覆盖的区域是一个连通块，所以可以把这些边拆成网格图上的边，这样边数只有 \(\mathcal O(nm)\) 条，然后考虑边权，也就是同时覆盖这两个点的 \(h_{i,j}\) 的最大值，考虑从 \((i,j)\) 走到 \((x,y)\) 每一步 \(h_{i,j}-h_{x,y}+p_{i,j}-\operatorname{dis}((i,j),(x,y))\) 都是单调不增的，所以只需要记 \(f_{i,j,k}\) 表示走到 \((i,j)\)，且上述值为 \(k\) 的 \(h\) 的最大值，然后四种方向都转移一遍即可，时间复杂度 \(\mathcal O(nm(p+\log nm)+q\log nm)\)。
CF566E
首先有结论：两个非叶子结点之间有边等价于存在两个集合的交集为 \(\{u,v\}\)。先证充分性，考虑找到一个 \(u\) 的不为 \(v\) 的邻点和一个 \(v\) 的不为 \(u\) 的邻点，它们集合的交集即为 \(\{x,y\}\)；再证必要性，如果存在两个集合交集为 \(\{x,y\}\)，若 \(x\) 不与 \(y\) 相邻，那么 \(x\) 到 \(y\) 路径上的点必然也在交集内，矛盾。那么我们知道了所有非叶子结点之间的连边，只需要考虑每个叶子结点 \(u\) 连向哪个点即可。显然含有 \(u\) 的所有集合最小的那个就是 \(u\) 自己的，将这个集合中所有叶子结点除去就是 \(u\) 所连向的点在非叶子结点构成的子图中的邻点，对于非叶子结点数量 \(>2\) 的情况这是唯一的，也就能直接确定了。对于非叶子结点数量 \(\le 1\) 的情况是简单的，\(=2\) 时所有叶子结点只会构成两种本质不同的集合，把在同一个集合内的连向相同的点即可。时间复杂度 \(\mathcal O(\dfrac{n^3}{w})\)。
P8500
先给出结论：假设存在 \(i<j,a_i>a_j\) 且 \((i,j)\) 能交换则不优且\(a\) 中的数必然都在 \(V\) 中出现过，证明直接调整即可。考虑 B 性质，即确定了一些位置填的数，那么其他位置必定单调递增，也就是只需要考虑填了的数与未填的数之间的贡献即可。从前往后填，假设填到 \(i\)，那么就是要找到 \(x\) 使得 \(\displaystyle\sum_{j<i}[a_j>x]+\sum_{j>i}[a_j<x]\) 最小，不难使用线段树维护，同时从前往后是将一个后面的移到前面，所以 \(x\) 必然单增，也自然就满足上面条件了。
现在考虑原问题，区间 \(\min=v\) 可以看做 \(a[l,r]\) 均 \(\ge v\) 且存在 \(v\)，那么先对所有区间进行 chkmax，得到 \(b_i\) 满足 \(a_i\ge b_i\)，然后如果有一个区间最小值 \(>v\) 那么无解。接着考虑这个 \(v\) 放到哪里，对于每个不同的 \(v\) 分别考虑，将所有区间按 \(l\) 从大到小排序，如果区间内已经放了 \(v\) 则可以跳过，否则就放在第一个 \(b_i=v\) 的地方，根据上面的结论这是正确的。
这样我们将题目转化为，有若干个地方钦定 \(a_i=b_i\)，其余地方 \(a_i\ge b_i\)，求逆序对最小值。类似 B 性质，依旧从前往后确定，可以通过调整法证明这是正确的。时间复杂度 \(\mathcal O((n+m)\log n)\)。
AGC058F
考虑如果式子中的 \(\dfrac{1}{n}\) 改成 \(\dfrac{1}{n-1}\)，那么可以归纳证明答案为 \(1\)，这个的组合意义就是选择一条边，将其删去，然后将两边看成独立的子问题，最终只剩 \(n\) 个孤点的概率。考虑给原问题也编一个组合意义，在每条边中间加一个点，然后将所有点重编号为 \(1\sim 2n-1\)，考虑以下问题：求给每个点赋 \(1\sim 2n-1\) 的点权，满足点权是一个排列，且使得所有边上的点的点权小于它相邻两个点的点权的概率。先思考一下这个问题如何计算：记答案为 \(g(t)\)，那么考虑 \(p_u=1\) 的点 \(u\) 必然是边上的点，将其删去后变成两个子树，不妨设为 \(t_1\) 和 \(t_2\)，那么有 \(g(t)=\dfrac{1}{2|t|-1}\displaystyle\sum_{u}g(t_1)g(t_2)\)，这个和原题的式子仅有 \(\dfrac{1}{2|t|-1}\) 的差别，考虑对于每个边上的点，给它挂 \(P-1\) 个儿子，那么这个系数就变成 \(\dfrac{1}{|t|}\) 了。对于这个的计算，考虑容斥。先随便找个根，然后钦定若干个边上的点小于其父亲，那么大小关系就构成了若干个外向树，对于每棵树要计算拓扑序除以 \(cnt!\)，也就是 \(\prod\frac{1}{sz_u}\)，直接记 \(f_{u,i}\) 表示以 \(u\) 为根子树目前 \(sz_u=i\) 的方案数，转移是简单的。时间复杂度 \(\mathcal O(n^2)\)。