A ARC214F Unpredictable Moves
jly：一般来说，网格图上点的连通性问题可以转化为对偶图的割的问题。
先不考虑不能在同一个方向走连续两步的限制，考虑如何用最小割建模。
不难发现，如果一组障碍可以使得 \((1,1)\) 和 \((n,m)\) 不连通，则一定是一组障碍八连通，且这些障碍中有一个在左下的边界周围，有一个在右上的边界周围。
这样我们令左下边界为 \(S\)，右上边界为 \(T\)，如果障碍之间以及障碍和边界之间八连通连无向边，则使得 \((1,1),(n,m)\) 连通则则需要使得 \(S,T\) 不连通。
这样把一个障碍点拆成容量为 \(1\) 的边，其余边为 \(+\infty\) 跑最小割即可。
考虑加入同一个方向不能走连续两步的限制，唯一发生变化的限制就是此时如果两个障碍在同一行或同一列，且中间空了一个格子，我们不能从这个格子穿过去，综合上面的讨论，我们让障碍之间以及障碍和边界之间曼哈顿距离 \(\le 2\) 的连无向边，再跑最小割即可解决。
注意 \((0,1),(1,0),(n,m+1),(n+1,m)\) 这四个点要脱离左下边界和右上边界，因为我们在 \((1,1)\) 只需要考虑走出去，而在 \((n,m)\) 只需要考虑走进去。
B QOJ7340 Spoonerisms
感觉是最简单的一题了。
考虑让每个字符串的前缀 \([1,i]\) 向后缀 \([i+1,|s_i|]\) 连一条无向边，得到一个二分图，注意左部点的字符串和右部点的字符串应当区分。
题目让我们求四元环，虽然 \(m\le 10^6\)，但我们四元环计数的 \(O(m\sqrt{m})\) 做法是知名的左手常数小，右手小常数。所以用一般图找四元环的方法来找二分图上的四元环。
每次要找四元环，我们枚举四元环里度数最大的那个点 \(x\)，枚举与他相邻且度数比他小的点 \(y\)，然后将 \(y\) 周围的所有点都打上标记 \(y\)，如果在枚举 \(x\) 的一个相邻点 \(y\) 时，遍历到 \(y\) 相邻点 \(z\) 时发现 \(z\) 有标记 \(w\)，\(x,y,z,w\) 为一个四元环。
考虑时间复杂度分析？设 \(x\) 的度数为 \(deg_x\)，则 \(y\) 给周围点打标机的复杂度为 \(deg_y\)，主要看 \(y\) 会被枚举到几次，这个次数是 \(\min(|\{x|deg_x>deg_y\}|,deg_y)\)，根号分治，根据 \(deg_y\) 与 \(\sqrt{m}\) 的关系，可以得到后半部分的 \(\min<\sqrt{m}\)，而 \(\sum deg_i =m\)，所以总复杂度为 \(O(m\sqrt{m})\)。
C The Imaginary Girlfriend
过于困难，jly 讲一半给自己 hack 了。
D QOJ7324 Eulerian Orientation
非常厉害的题。
考虑一个连通的图有多少个子图是欧拉图，我们先任意钦定一颗搜索树，对于剩下的非树边 \(m-n+1\)，无论我们怎样染色，最终导致树中的点度数此时为奇数或偶数，我们都可以通过每个点连向父亲的点的染色来改变奇偶性，因为一个图的度数和为偶数，所以从下往上操作到根时，根一定符合条件。
所以 \(c\) 个连通块的图通过染色得到的欧拉图的方案数为 \(2^{m-n+c}\)。
考虑如何对 \(x^2\) 计数？我们考虑 \(x^2\) 的实际意义，就是确定一个染色方案后，枚举其中任意两条红边，事实上，我们改变枚举顺序，先任意枚举两条红边，在考虑有多少个染色方案包含这两条红边。考虑选择两条红边 \(e,f\)。
如果 \(e,f\) 之一是割边，则无合法方案：命题等价于欧拉图不含割边，考虑将原图分为两个部分，先将割边连接，此时左右两个部分各有一个奇度点，其余均是偶度点，每次加一条边，只可能导致一侧某两个点奇偶性同时发生变化，两侧始终有一个奇度点，所以无解。
考虑 \(e=f\) 的情况，此时 \(e,f\) 可以看做一条非树边，固定一条边的颜色后方案数为 \(2^{m-n+c-1}\)。
考虑 \(e\ne f\) 的情况，若 \(\{e,f\}\) 不是割集，则此时 \(e,f\) 可以看做两条非树边，固定一条边的颜色后方案数为 \(2^{m-n+c-2}\)。
若 \(\{e,f\}\) 是割集，考虑删掉这两条边，分别求出内部生成树，边数减二连通快数加一，再加上两条边，两条链的奇偶性发生两次变化，仍然合法。
好的，问题是快速求出割边和两个边的割集。对于求割集，我们可以将非树边随机权值，让非树边向他覆盖的树边都异或上这个权值（使用树上差分），则一个集合 \(S\) 为割集等等价于集合内各边异或和为 \(0\)，证明是神秘线性代数推导我不会。
两个边的割集就是 \(w_e=w_f\)，同理，在树上差分的过程中，若一条树边权值为 \(0\)，则该树边是割边，然后统计去做就行了，时间复杂度为 \(O(n)\)。
E ARC156F Make Same Set
考虑这样一个过程：
\(\forall i \in [1,n]\)：将 \(A_i\) 或 \(B_i\) 加入集合 \(S\)，或什么都不做。
\(\forall i \in [1,n]\)：将 \(A_i\) 或 \(C_i\) 加入集合 \(T\)，或什么都不做。
最后最大化 \(|S\cap T|\) 的大小。可以用网络流，相当一第一轮往 \(S\) 加数，第二轮往 \(S\) 取数，看最大取多少。
网络流，\(\forall x \in [1,n]\)，连 \(S\to in_x,out_x\to T\) 的边，连 \(in_x\to w_{A_x},in_{x}\to w_{B_x},w_{A_x}\to out_x,w_{C_x}\to out_x\) 的边，再在 \(w_{A_i}\) 拆成出点和入点，中间连边（保证集合不重复），然后边权均设置为 \(1\) 跑最大流。
但这样做是有问题的，我们什么都不做的话有一个前提，就是集合中已经包含了 \(A_i,B_i\) 之一或已经从集合中取走了 \(A_i,C_i\) 之一。
然后根据 dinic 算法每次只会增广最短增广路，我们只需要初始选择所有 \(A_i\)，然后暴力增广，就能保证上述情况不会发生。
时间复杂度类似二分图最大匹配的网络流方法，复杂度为 \(O(m\sqrt{n})\)。
F CF1517G Starry Night Camping
注意力惊人。我们规定：
-
\(x\) 奇，\(y\) 偶为 \(1\) 类点。
-
\(x\) 偶，\(y\) 偶为 \(2\) 类点。
-
\(x\) 奇，\(y\) 偶为 \(3\) 类点。
-
\(x\) 偶，\(y\) 偶为 \(4\) 类点。
任意四个不合法帐篷组成的图形可以看成其内部 \(1\to 2\to 3\to 4\) 的路径。
对于 \(1\le x<4\)，我们让所有 \(x\) 向其相邻的 \(x+1\) 类点连边。\(S\) 向 \(1\) 类点连边，\(4\) 类点向 \(T\) 连边。
我们要做的就是割掉一些点使得 \(S\to T\) 的路径不存在。于是把点拆成边，边的容量为拆点的代价，其余边容量均为 \(+\infty\)，这个题就变成最小割板子了。
G AGC033F Adding Edges
若存在边 \((u,w),(u,v)\) 且 \(u,v,w\) 在一个路径上，显然将 \((u,w)\) 换成 \((v,w)\) 不会影响答案。
进一步可以发现，这些段越零碎越灵活，所以我们考虑将原图 \(G\) 中所有满足上述条件的边处理，得到 \(G'\)，则最终在图中的边 \((u,v)\) 一定是 \(G'\) 中若干个边收尾拼在一起组成的。
得到 \(G'\) 后 \(O(n^2)\) 随便计算，如何正确得到 \(G'\)？考虑增量法动态加边。
我们设 \(f(t,x)\) 表示 \(t\) 为根下与 \(t\) 相连的 \(x\) 的深度最大祖先。
每次我们先仿照上面的模式，尽可能减小 \((u,v)\)，再去更新 \(f\) 数组，在更新的过程中，可能会有 \((u,w)\) 这种之前加入时已经减小的最小，现在加入 \((u,v)\) 后又可以继续减小，那我们就重新加入继续减小。
更新 \(f\) 数组可以做到 \(O(n^2)\)，每一条边虽然可能多次加入，但只会不断减小，均摊也是 \(O(n^2)\) 的。
H ARC170F Edge Deletion 2
鸽了，已经没有可以思考的心智了。
I QOJ8800 Triinformathlon
不难发现把最基础的偏序关系当成边后，我们得到了一个竞赛图。
对于这种具有查询传递性的问题，考虑bitset缩点。
竞赛图有一个很好的性质，一定存在一条路径经过 \(1\sim n\) 的点恰好一次，我们考虑把这个链提取出来，这样缩点就是把链上的一段区间缩成一个点。
结论就是 P10451，实现可以用 stable_sort 自定义函数快速找路径。
接下来，我们找出每个人 \(i\) 在路径上的位置 \(rk_i\)，我们要找他能偏序的，最小的 \(rk_i\) 是什么。
这一部分实际上是三个二维偏序分开处理一下就行，最后我们倒着往前用并查集合并在同一个强联通分量的点。
对于询问，在一个强联通分量可以互相偏序，不在的话就比较 \(rk_i\)。然后就做完了。
时间复杂度为 \(O(n\log n)\)。
J QOJ406 Sandwich
很奇怪的题。
显然，我们如果拿走了一个方格中的三角形 \(x\) 后，另一个三角形 \(y\) 就能直接拿出来，我们考虑两个三角形分别求出单独拿出来的花费 \(A,B\)，答案即为 \(\min(A,B)+1\)。
现在，我们的任务变成了了拿出一个三角形 \(x\)，因为我们已知 \(y\) 在 \(x\) 后拿出，考虑拿走 \(x\) 两个直角边三角形 \(a,b\)。
我们要拿出三角形 \(a\)，但 \(a\) 直角边相对的三角形 \(x\) 在其之后拿出，所以我们必须先拿走 \(a\) 的对角线相邻三角形 \(c\)。
不难发现，我们实际上在不断递归解决子问题，我们让相邻的两个三角形连无向边，并根据两三角形是直角边相邻还是斜边相邻分类，则拿出一个三角形 \(x\) 的花费为从 \(x\) 出发，第一步只能走直角相邻的边，接下来每一步走的边不能和上一步类型相同，能走到的点的个数。
如何判断无解？如果我们推导出了想拿出 \(a\) 就要先拿 \(b\)，想拿出 \(b\) 就要先拿出 \(a\) 的结论则无解，体现在上述 DFS 过程中就是我们将当前递归中的点加入栈，但我们下一步要走到一个栈中的节点，此时就是无解。
为了保证时间复杂度，一个点如果可以正常完成递归，则第二次要搜索他时就不搜索他了，需要用数组标记。时间复杂度为 \(O(n^4)\)。
考虑优化，注意到我们的无向边在一横行里面完整的连接了所有的三角形，一些三角形第一步总是往右走，我们就把这些三角形放在一起处理，每次从右往左一个一个 DFS，但每次 DFS 都继承上一次的标记数组。同理对于往左的也是如此，时间复杂度为 \(O(n^3)\)。
注意到常数巨大无比，我们发现 vector 存图太慢了，但是 DFS 过程中一个点只可能走两类边，走斜边相邻的边容易求得另外一个为一点的编号，走直角相邻边就用 \(nm\) 个长度为 \(2\) 的数组存储即可。然后就跑的很快了。