闲话
【碎片】0.8/1
明天集训就结束了（
同学们吃外卖吃够了吗（
模拟赛
T1
会维护静态区间子区间 mex 和吧？不会？会维护静态区间 mex 吧？套个历史版本和就没了。
mex 是最小，mix 其实就是次小。因此支持一个覆盖最小、覆盖次小，并对次小支持一个历史版本和即可。
总复杂度 \(O(n\log n)\)。
T2
注意到我们只需要设计一条 \(X\to x, Y\to y\) 的路径，满足 \(x = y\) 或 \(x, y\) 的度数不同。这样要么可以区分出初始点，要么终点相同。
场上的做法正确性不会证。注意到(?)这两条路径每次跳的出边必须在 vector 中编号相同。这样我们暴力遍历所有可能的路径是 \(O(n)\) 条。找出一条满足上面条件的路径并记录，如果 \(x = y\) 直接移动即可。反之可以区分出初始点。
总时间复杂度 \(O(n)\)，但是正确性好像不是很有。跑一遍跑不出来就把 \(X, Y\) 交换一下再跑一遍。
正解不会
T3
可以发现，每个点对不平衡度的贡献是独立的，我们只需要对每个点分别计算答案，最后用 max 卷积合并即可。
对单独一个点，我们不妨考虑容斥，转化成不平衡度不超过 \(k\) 的方案数。由于这也就是每次在两侧找一个子树加点，我们可以把他放在二维平面上转成游走问题。
考虑这就是计数从 \((0, 0)\) 到 \((n, m)\)，即左右子树大小；放左子树是向右，放右子树是向上；不经过 \(y = x - k + 1, y = x + k - 1\) 的路径数。
两条线卡路径可以转化成镜面反射容斥，发现答案就是
这个式子可以 \(O(n/k)\) 地计算。题解说一个点的 \(k\) 和更小的子树大小同阶，因此可以分析到 \(O(n\log^2 n)\)。
杂题
一张图分为两部分，左右都有 \(n\) 个节点，\(A_i\rightarrow A_{i+1}\) 连边，\(B_i\rightarrow B_{i+1}\) 连边，容量给出。
有 \(m\) 对 \(A_i\rightarrow B_j\) 有边，容量给出。
你需要先求出原图从 \(A_1\) 到 \(B_n\) 的最大流，然后有 \(q\) 次操作，每次操作给出 \(i\)，先修改 \(A_i\rightarrow A_{i+1}\) 的边的容量，然后询问从 \(A_1\) 到 \(B_n\) 的最大流。
\(2\leq n,m\leq 2\times 10^5\)，容量\(\ \leq 10^9\)。
感谢 @Broken_Eclipse 大佬推的题！
根据最大流最小割定理，将答案转化成最小割。考虑最后答案的形式。
我们发现，最优解一定是 \((a, a)\) 割一条，\((b, b)\) 割一条，\((a, b)\) 割若干条的形式，因为这一定不劣。所以考虑构造这形式的解，取最小值一定能得到答案。
假设左边割了 \(A_i\to A_{i + 1}\)，右边割了 \(B_j\to B_{j + 1}\)，那我们需要割掉的 \(A\to B\) 一定形如 \(A\le A_i, B_{j + 1} \le B\)，这画个图就能理解了。而且可以发现，确定 \((i, j)\) 后要割掉的 \(A\to B\) 是确定的。我们不妨枚举一个 \(i\)，计算最小的 \(j\)。
对一个 \((i, j)\)，具体的形式是
\[\text{cost}(A_i\to A_{i + 1}) + \text{cost}(B_j\to B_{j + 1}) + \sum_{x = 1}^i \sum_{y = j + 1}^n \text{cost}(A_x\to B_y) \]考虑确定一个 \(i\)，\(\text{cost}(A_i\to A_{i + 1})\) 的贡献是不计的，而且剩下的部分是静态的，因此在整个过程中，\(i\) 对应的 \(j\) 是确定的一个，可以预处理。
预处理的方式就是线段树。这个形式应该比较好构造，复杂度大致是 \(O(n + m\log n)\)。记 \(i\) 对应的 \(j\) 是 \(i_2\)。
设
\[g(i) = \text{cost}(B_{i_2}\to B_{i_2 + 1}) + \sum_{x = 1}^i \sum_{y = i_2 + 1}^n \text{cost}(A_x\to B_y) \]根据上面的内容，这是已经处理出的。并记 \(f(i) = \text{cost}(A_i\to A_{i + 1})\)。
因此我们就需要支持单点修改 \(f(i)\)，支持查询 \(f(i) + g(i)\) 最小值。仍然是线段树。
总时间复杂度 \(O(n + (m + q)\log n)\)。
标签：21,闲话,sum,cost,23.3,text,rightarrow,复杂度,log From： https://www.cnblogs.com/joke3579/p/chitchat230321.html