shortest

先求出这张 DAG 的拓扑序。考虑删掉一个节点后从 S 到 T 的最短路，它的构成一定是 S + 一些拓扑序递增的节点 + 一条拓扑序跨过被删掉节点的边 + 一些拓扑序递增的节点 + T。那么这条路径是可以由那条跨过被删掉节点的边来表示的。在线段树上区间修改，询问时单点求值即可。

chess

考虑网络流的行列建图模型，在交点处连边。但我们发现有障碍的隔开的两段是不会影响的，所以我们把所有连续的段单独拎出来建点。发现一个段里选第 k 个点对答案的贡献是 k-1，所以源点 / 汇点向每段连流量为 1，费用为 0,\cdots,len-1 的边即可，len 表示段长。然后跑流量为 k 的最小费用流即可。因为费用是递增的所以这个建图是对的。

但是每次询问跑一遍费用流复杂度肯定是不对的，所以考虑从小到达枚举 k，每次在之前的残量网络上增广 1 的流即可。

tower

有一个暴力的思路是 n! 枚举塔的相对位置关系然后分别用组合方法计算。假设第 i 个塔的编号是 p_i 的话，我们发现这个答案只与这个式子有关：

实际上由隔板法可以求出答案为 \binom{l-k+n-1}{n}。我们知道 k 的上界是 O(n^2) 的，所以我们可以对每个 k 分别求出有多少种情况，然后再乘上它即可。

考虑 DP，如果按位置顺序依次加入每个塔的话，是需要状压前面选了哪些塔的，这个复杂度显然不对。所以我们换一种思路，按高度从大到小的顺序加入塔。这看似还需要记录之前加入的塔的相对顺序，实际上是不用的。我们只需要记 f(i,k,j) 表示加入了前 i 高的塔，当前的 k，且这里有 j 个空位需要继续插入更低的塔。转移考虑插入一个塔，它会选择 j 个空位中的一个插入并消除这个空位，然后又会产生 0-2 个空位。分别讨论：

• 如果产生了 0 个空位，那么这个塔对 k 没有贡献，转移为 f(i+1,k,j-1)\gets j\cdot f(i,j,k)；
• 如果产生了 1 个空位，那么这个塔对 k 会有一次自身高度的贡献，而且这个空位有在左边和右边两种情况，因此转移为 f(i+1,k+(n-i),j)\gets 2j\cdot f(i,j,k)；
• 如果产生了 2 个空位，那么这个塔对 k 会有两次自身高度的贡献，因此转移为 f(i+1,k+2(n-i),j+1)\gets j\cdot f(i,j,k)。

最后统一计算即可。