P4766
不难发现时间的先后顺序是不重要的。所以把时间转化到数轴上。
数据范围提示区间 dp，设 \(f_{l,r}\) 表示 \([l,r]\) 时间里面全部消除的代价。
\(f_{l,r}=\max(f_{l,k}+f_{k,r}+d_{l,k,r})\)，其中 \(d_{l,k,r}\) 表示跨越 \(k\) 的，且在 \([l,r]\) 里最远的距离。
然而 \(d\) 的处理要四次方。
考虑钦定一个区间内距离最远的最后消除，\(O(n)\) 找到 \(id\)，
那么 \(f_{l,r}=\max(f_{l,k-1}+f_{k+1,r}+d_{id})\)，满足 \(k\) 在 \(id\) 这个区间里。
P5933
设 \(f_S\) 表示 \(S\) 任意连边的方案数，\(g_{S}\) 表示 \(S\) 点集联通的方案数。
考虑容斥，求出 \(h_S\) 表示 \(S\) 点集不合法的方案，\(g_S=f_S-h_S\).
我们对于 \(h_S\)，为了不重复，先随便取出一个点 \(p\)，枚举 \(p\) 所在连通块 \(P\)，设 \(T=C_SP\).
那么 \(h_s=\sum dp_P\times f_T\)，\(T\) 不能为空集。
P4198
我们要维护的是一个下凸壳，则每个点到原点的斜率递增。
线段树维护，我们假设现在线段树维护好了一些区间，如何去合并。
关于合并两个区间，首先要记录一个区间的最大斜率 \(Mx\) 和凸壳点的个数 \(len\)。
左边区间必选，我们现在要找右边的第一个斜率大于左边 \(Mx\) 的点，给它接上去。
线段树上二分。如果往右走，那么继续递归；往左走，加上右边的贡献，是 \(len_p-len_{ls}\).
P5307
首先有朴素的状态 \(dp_{i,j,k}\) 表示到 \((i,j)\) 这个点，当前乘积是 \(k\) 的方案数，明显裂开。
考虑优化状态，\(dp_{i,j,k}\) 表示还要至少乘上 \(k\) 才能不小于 \(n\) 的方案数。
整除分块，\(k\) 的个数是 \(\sqrt n\) 级别的。