题解：CF1427G One Billion Shades of Grey

首先考虑边缘的数值域只有 $2$ 怎么做。考虑网络流，通过让 $i$ 与 $S$ 连通来代表 $i$ 选 $1$，与 $T$ 连通代表 $i$ 选 $2$。相邻的两个点连一条权值为 $1$ 的双向边。不考虑边界上已经确定的点，用与 $S/T$ 直接连边替代与它们连边。这样就能做到 $O(n^2)$ 了。

显然存在一个最优解，你需要填的数就是边缘出现过的数。

（具体不会证明）

有了这个断言，于是就可以枚举扫描线的 $v$ 的范围（显然有 $n$ 个）。最开始求一遍网络流是 $O((n^2)^{1.5})$，即 $O(n^3)$。观察到所有点的流量都为 $1$，并且边变化的条数只有 $O(1)$，于是考虑退流。

具体地，当需要删掉一条边的时候，假定该边有流量，且设流量方向为 $(u,v)$，则先将全局最大流减去该边流量，则跑一遍以 $u$ 为源点，$S$ 为汇点的最大流，然后再跑一遍以 $T$ 为源点，$v$ 为汇点的最大流。最后再跑一次最大流，把求得的数值加到全局最大流上。一轮增广复杂度为 $O(n^2)$，会变化 $n$ 次，所以时间复杂度仍为 $O(n^3)$。

卡常方面：

首先把 #define int long long 关了。

其次手写队列。

最重要的一点：由于删除边最多只会影响一条到 $1$ 到 $u$，$v$ 到 $n$ 的流量，而删边与加边会导致的流量变化只有 $1$，所以可以直接使用 EK，省去 Dinic 的一次 dfs。