感觉阳了之后没完全好啊，非常想睡觉。
以后这个东西把三天放在一起吧，感觉每天都更有点多的（
P3488 [POI2009]LYZ-Ice Skates
Description
给一张二分图，其中左边第 \(i\) 个点和右边 \([i,i+d]\) 有边，有数组 \(a_i\)，构造一张网络，使得 \(S\) 到左部所有点有流量为 \(a_i\) 的边，右部所有点到 \(T\) 有流量为 \(k\) 的边。\(q\) 次修改，每次修改一个 \(a_i\)，求修改之后能否满流。
Analysis
直接流可以 \(\mathcal{O}(qn^2)\)，使用退流可能会快一点。
考虑用 Hall 定理，现在问题就是最小化 \(|N(S)|-|S|\)。考虑 DP，设 \(f_i\) 表示最后一个选 \(i\) 的答案，每次枚举下一个数，容易求出 \(|N(S)|\) 的变化。使用一些技巧不难优化到 \(\mathcal{O}(qn)\)。
观察一下 \(|N(S)|\) 的形态，发现它构成若干段区间，如果它们满足任意一个都 \(\geq 0\)，它们的并一定满足条件。所以只需要考虑 \(|N(S)|\) 为单个连续区间的情况，假设是 \([l,r]\)，那么 \(S\) 选 \([l,r-d]\) 一定是最优的。问题就变成了选择区间 \([l,r]\)，最小化 \((r-l+1+d)k-\sum\limits_{i=l}^r a_i\)，容易转化成最小子段和问题，用线段树维护即可。
CF765F Souvenirs
Description
给定序列 \(a_i\)，\(q\) 次询问 \([l,r]\)，求 \(\min\limits_{i,j\in[l,r],i\neq j}|a_i-a_j|\)。
Analysis
之前听过这题，知道大致思路。
直接暴力枚举可以 \(\mathcal{O}(n^2)\)。
最优化问题的一个思路是：删去一些无用的点对来降低复杂度。考虑哪些点是无用的。发现对于单个点 \(x\)，假如它连了一个 \(y\)，不妨设 \(a_y>a_x\)，那么下个位置 \(a_z\) 满足 \((x,z)\) 有用等价于 \(a_z-a_x<a_y-a_z\)，移项就是 \(a_z<(a_x+a_y)/x\)，所以对于单个位置最多 \(\mathcal{O}(\log V)\) 个有用的值。把这些值提出来做二维数点即可。
还有一点是求出一个位置前面的最大的值域在 \([l,r]\) 内的位置没必要二分，直接动态开点线段树上维护就行。
启示：最优化问题可以只保留有用的对象，删除无用的对象。
P5333 [JSOI2019]神经网络
Description
给定 \(m\) 棵树，构造一张图，保留所有的树边，并在不同树的任意两个结点之间连一条边，求哈密顿回路数。
Analysis
想了一年！好像会了个反演做法，还不知道对不对，明天更。