A
\(n\times n\) 的平面上有 \(m\) 条通道，从 \((a_i,b_i)\) 到 \((c_i,d_i)\)，代价为 \(|a_i-c_i|+|b_i-d_i|-1\)。
同时你可以花 \(1\) 的代价移动到四联通的点。问所有点之间两两最短距离之和。\(n\le 1e9,m\le 500\)。
走一条通道可以减少 \(1\) 的代价，我们先求出所有的代价。
离散化，把整个平面分成 \(O(m^2)\) 个区域。
有一个朴素的 dp，设 \(dp_{x,y,s,t}\) 表示 \((x,y)\) 到 \((s,t)\) 能减少多少代价。
转移可以从 \(dp_{x,y,s-1,t},dp_{x,y,s,t-1}\) 转移。复杂度 \(O(m^4)\)。注
注意到 dp 的值不超过 \(m\)，考虑缩减状态，计算 \(dp_{x,y,k}\) 表示以 \(x,y\) 为起点经过 \(k\) 个通道能到的面积。
这个面积一定是若干个左下角为某终点，右上角为 \((n,n)\) 的矩形并，再把 \(k+1\) 的面积扣掉即可。
问题是怎么算出 \(x,y\) 为起点经过 \(k\) 个通道最后的终点有哪些，只需要求 \(x,y\) 到每个通道的距离。
这个还是 dp，用我们第一个的朴素 dp 即可。
B
给定一棵树，每条边有黑白的区分，每次询问一个点只走黑边能到多少个点，或反转链上边的颜色。
\(n\le 10^5\)。
动态 dp。每次询问也就是求联通块大小，我们先把连通块顶端的点二分找出来。
树链剖分，每个点维护其所有轻儿子的权值和即可。
C
有一个序列 \(A\)，我们依此生成一个序列 \(B\)，每次把 \(A_i\) 放进 \(B\) 的最左边或最右边。（两种方案）
问 \(B\) 严格上升子序列最长是多少，以及生成的方案数。
考虑我们一开始 \(B\) 有一个 \(A_1\)。我们放在 \(A_1\) 左边的，从右到左编号递增；放在 \(A_1\) 右边的反之。
我们猜想只需要把 \(A\) 倒过来，再拼上 \(A\)，求最长上升子序列即可了。
因为求得是严格上升子序列，所以一个元素注定不会计算两次。
一个元素是在左边被选的还是右边被选的对应两种情况。