只做完了
场切的几题
A - Advertisement Matching
(N) 个广告，(M) 个人，第 (i) 个广告需要分给 (a_i) 个人观看，第 (i) 个人只能收到不超过 (b_i) 个不同的广告。(Q) 次操作，每次选择一个 (a) 或 (b) 增加或减少 (1)，每次操作之后求问能否把所有的广告都分配完。(N,M,Q,a_i,b_ile 2.5 imes 10^5)。
首先不难看出一个二分图模型：第 (i) 个左部点需要匹配 (a_i) 个右部点，第 (i) 个右部点最大匹配 (b_i) 个左部点。然后判断是否存在方案使所有左部点都匹配完。
接下来引入一个 Gale–Ryser 定理，在本题中可以写成：先将 (a) 降序排序，那么若存在方案，当且仅当 (forall kin[1, N]) 都有 (sum_{i=1}^k a_ile sum_{i=1}^M min(b_i,k)) 成立。下面是证明：
先建立网络流模型：源点向左边连边，容量 (a)；右边向汇点连 (b) 容量边；左右部点之间都连一条 (1) 容量边。现在需要证明最大流 (ge sum_{i=1}^N a)，等价于最小割 (ge sum_{i=1}^N a)。
考虑一个割，源点这边左部点记作 (S)，右部点记作 (T)。那么最小割可以表示为：
[sum_{i otin S} a_i+sum_{iin T} b_i + |S| imes(M-|T|) ]令 (|S|=k)，那么将 (a) 降序排序后（记作 (a')）有：(min_{S}{sum_{i otin S} a_i} = sum_{i=1}^k a'_i)。而后两个和式又可以写成 (sum_{iin T}b_i+sum_{i otin T}k)。贪心地考虑，要使其最小化，那么一定将大于 (k) 的那些 (b_i) 换为 (k)。那么最终最小割为：
[sum_{i=1}^k a'_i+sum_{i=1}^Mmin(b_i,k) ]
然后就对于每个 (k)，维护出 (sum_{i=1}^M min(b_i,k)-sum_{i=1}^k a_i) 即可。这个 (min) 非常恶心，考虑一个巧妙的转化：设 (c_k = sum_{i=1}^M [b_ige k])，即不小于 (k) 的 (b) 的个数。我们发现原式 (=sum_{i=1}^k (c_i-a_i))，简洁了许多，可以线段树维护。那么怎么修改呢？
- 对于修改 (b)，由于只有 (1) 的变化量，不难发现只需要修改 (c) 的一个位置就行；
- 对于 (a)，我们可以在排好序的 (a') 上找到第一个或最后一个对应值的位置（二分），然后直接在 (a') 上改掉。由于变化量为 (1)，不会改动原来 (a') 的降序。
最后复杂度为 (O(Nlog N))。
C - Economic One-way Roads
给定一个 (N) 个点的无向图，每条边需要被定向，(a_{i,j}) 表示将 (i,j) 之间的边定向为 (i o j) 的费用。如果 (a_{i,j}=-1) 说明原图中不存在连接 (i,j) 的边。你需要用最少的总费用给原图中的边定向，使得整张有向图强连通。(Nle 18,a_{i,j}in[-1, 10^6])。
首先需要知道，一张图强连通，当且仅当可以通过以下方式构造：
维护一个点集 (V)，首先任意选择一个点 (v)，加入 (V) 中。然后重复执行以下操作：
- 在 (V) 选出任意两个点 (x,y)（(x) 可以等于 (y)）；
- 找出若干个 ( otin V) 的点 ({u_1, u_2, cdots, u_k})（可以不选任何的点），然后连接 (x o u_1 o u_2 ocdots o u_k o y)，并将 ({u_1, u_2, cdots, u_k}) 加入点集 (V)。
这种方法被成为“耳分解”，上面每次选出的那个路径就是“耳”。
根据这个我们有一个朴素的状压 dp：(f(S)) 表示选出点集 (S) 构成强连通图的最小选择的总边花费和。那么对于每个状态 (f(S))，都可以枚举一遍 (S) 补集的子集作为“耳”，然后还有 (O(|S|^2)) 种方法选择“耳”的两端。总复杂度为 (O(3^N N^2))。
这样的方法不仅需要优化，而且存在正确性的问题：可能存在一条边正反都没有记入答案，从而结果偏小。有一种巧妙的解决方法是：对于一条未定向的边，两个方向的花费分别为 (a,b)。这总得选一条吧？那么不妨先将 (min(a,b)) 加入答案，然后把两个方向分别用 (a-min(a,b))，(b-min(a,b)) 计算。这样就能直接拆开了。
考虑优化：引入 (g(S,u,v)) 为当前构造的“耳”还需要一条连接 (u,v) 的路径，强连通部分以及 (u,v) 的非完整“耳”构成的点集为 (S)。容易发现，记录“耳”的端点的好处在于，可以直接从 (u,v) 开始拓展而不是盲目地枚举集合。
复杂度可以做到不超过 (O(2^N N^3))，当然实现转移还是有及其多的细节的。
D - Just Meeting
求构造一个 (N imes N) 的矩阵 (C)，满足 (forall iin [1, n])，都满足 (forall) 不同于 (i) 的 (j,k(j e k))，有 (C_{i,j}ge min(C_{i,k},C_{k,j}))。并且 (C_{i,j}=C_{j,i})。现有 (M) 个位置已经有固定值，除这些位置外都可以任意选择数字。求所有可行构造方案中 (sum_{i=1}^nsum_{j=i+1}^nC_{i,j}) 的最小值。(N,Mle 3 imes 10^5)，方案中的 (C_{i,j}in [1, 10^7])。
如果将 (C) 矩阵看做图的邻接矩阵的话，那么相当于要构造一个 (N) 个点的完全图，满足 (forall i e j)，不存在一个 (k) 使 (C_{i,j}le min(C_{i,k}, C_{k,j}))。也就是说 (i,j) 间不存在一条长为 (2) 的路径其上最小比边权小于 (i,j) 之间的边。
考虑一个三元组 ((i,j,k))，要使之满足条件，不得存在一条边严格小于其他两条边。那么小小讨论一下：
- 三点间不存在边：要求最小化 (C) 的总和必然是三个 (1) 啦；
- 只存在一条边：另外两条也是 (1)；
- 存在两条：由于新加入的边不能作为最小的，原来两条中最小的也不能让它一个最小，于是新边权必然为原来两条中的较小者；
- 存在三条：现在就由不得选了，反而应该检查是否合法。
那么拓展到多个点的情况，可以重复以上加边操作，直到补成完全图。可以证明不会因为补上的边突然违反约束。
不难发现，倘若我们先求出一个原图的最大生成森林，对于一条未补上的边 ((i,j))，树上路径的最小值（原图的瓶颈路）就可以作为这条新边的权值。对于原来存在但不属于最大生成森林的边，其边权应该与树上路径的最小值相等：如果小了那么它会成为某个三元环的唯一最小值，大了又会导致路径上那条最小边成为唯一最小值。
最后实现的话，掏出一个 Kruskal 重构树就没了。复杂度 (O(Nlog N))。
E - Chemistry
给定一个 (N) 个点 (M) 条边的无向图，求有几个区间 ([l,r](1le lle rle n))，满足仅保留编号 (in[l,r]) 中的点可以恰好构成一条链。(N,Mle 2.5 imes 10^5)。
“一条链”的条件是很复杂的，考虑进行拆解：
- 没有环；
- 每个点度数不超过 (2)；
- 连通块个数为 (1)；
很显然这三个限制叠加就和链的限制等价，那么考虑对于每个右端点 (i)，左端点最前面可以达到什么位置，使得这个区间不存在环，定义为 (f_i)。同理对第二个限制定义 (g_i)。
假设通过某种手段求出了 (f,g)，那么只要统计有几个 (jin [min(f_i,g_i),i]) 满足区间中的点只有一个连通块即可。根据“点减边”的套路，我们可以维护每个左端点与当前右端点的点减边结果，计算有几个是 (1) 就行了。考虑线段树维护这个东西，每次右端点右移，左侧的所有值 (+1)，然后遍历当前右端点的边将边的影响加上即可。怎么维护出 (1) 的个数呢？注意到一张不空的图的连通块不可能有 (0) 个或者更少，也就是说 (1) 是可能的最小值，而最小值的个数维护有手就行。这部分复杂度 (O(Nlog N))。
考虑求 (f,g) 怎么搞。首先一个重要的性质：如果 ([j,i]) 不合法，那么 (forall k<j, [k,i]) 都不合法。掏出一个双指针，用一个 LCT 整出 (f)，开个桶整出 (g) 就行了。这里复杂度 (O(Nlog N))。
最后思考一个问题：为什么预处理的 (f,g) 不能适用第三个限制？因为连通块个数并不随着左端点的左移而单调不增或不减。
F - Interval Graph
给定 (N) 个闭区间，第 (i) 个为 ([s_i, e_i])，权值为 (w_i)。定义这 (n) 个区间组成的“区间图”为，(i, j) 之间存在一条无向边当且仅当 ([s_i, e_i]cap[s_j,e_j] e varnothing)。现在要求移除其中若干个区间，使剩下区间构成的区间图为森林。求保留区间权值和的最大值。(Nle 2.5 imes 10^5, 1le s_ile e_ile 5 imes 10^5,w_iin [1, 10^{12}])。
首先考虑一些区间的区间图是森林意味着区间之间有什么特征：森林说明没有环，而一个区间图不存在环的充要条件是：不存在一个位置 (p)，使得存在三个互不相同的 (i, j, k) 满足：(pin [s_i, e_i]cap [s_j, e_j]cap [s_k, e_k])。也就是说不能有一个位置上面覆盖三个及以上个区间。
那么我们考虑一个网络流模型：
- 一开始我们有 (2) 的流量：一个位置最多可以同时存在两个区间。
- 对于每个区间 ([s_i, e_i])，我们要走就会把他走完，那么连边 (s_i o (e_i + 1))，容量为 (1)，表示在 ([s_i, e_i]) 的位置这个区间我们可能会消耗一个流量。费用显然为 (w_i)。
- 对于每个位置 (p)，连边 (p o (p+1))，容量为 (2)，表示兼容该位置选零到二个区间三种情况。
然后发现要保留尽量大的，于是将费用取相反数，就可以跑费用流了。
然后 SPFA 貌似死了，考虑使用 Dijkstra，但很显然有负权，而传统解决方案中的势能需要 SPFA。
但是我们发现这个图是个 DAG！所以 dp 一下就可以求出势能了。
还有更简单的方法：设第 (i) 个位置的势能为 (-10^{12} imes i) 即可。但是这个我写炸了
最后时间复杂度 (O(Nlog N))。
H - Alchemy
有一个可重集合，元素 (i(in[0, N ))) 有 (c_i) 个。每次可以选择一个子集 (S)，在原集合中删去这些元素，重新插入一个 ( ext{mex}(S))。求最终可以得到的最大的权值的元素。(Nle 10^5)。
考虑将操作倒过来：每次选定一个元素 (k)，然后：
- (k=0)：插入任何数量的任意 (>0) 的元素；
- (k e 0)：插入任意数量（(>0)）的 (<k) 的元素，(>k) 的随意。
如果以上操作若干次之后得到了原集合的子集那么 (k) 是可行的。
实际上可以将上面操作简化：
- ({k} o {t| 0le t< k}(k>0))
- ({0} o {k}(k>0))
很显然新加入的多了不会比少了更容易成为原集的子集，于是这样简化是正确的。
那么对于一个 (k) 从右往左扫一遍就能 (O(N)) 判断是否可行。
然后发现这个东西单调，可以二分答案，复杂度 (O(Nlog N))。
J - Remote Control
在一个二维平面上，有一个在 ((0,0)) 处的障碍。一开始给定一个操作序列，长度为 (N)，序列中的每个操作为上下左右只一。现有 (Q) 次询问，每次在 ((x,y)) 放一个遥控车，并执行一次操作序列，遇到前面有障碍则忽略这一次操作。求最终位置。(N,Q,|x|,|y|le 3 imes 10^5)。
考虑每次移动车的复杂度是 (O(NQ)) 的，无法承受。那么不妨换个角度：车有很多个，但障碍只有一个对吧。那倒不如，直接一次性放完所有的车，然后用障碍去推，而不是用车去模拟。
具体的，先保存所有车的信息，然后对障碍执行操作序列，只不过都是反操作（左对右，上对下）。如果碰到了有车的位置，那么把这些车往对应方向再挤一个单位。
实现时可以用一个 std::map<std::pair<int, int>, std::set<int> > 保存每个位置对应的车的集合，推车时做一遍 std::set 的启发式合并就能保证复杂度。
最后算答案时，将期望移动到的位置算上推车的影响即可。复杂度 (O(Nlog^2 N))，当然也有 (O(Nlog N)) 的方法。
K - Sewing Graph
有一块布，上面有 (N) 个点 ({(x_i,y_i)})，你需要求一个序列 ({s_i})，设长度为 (K)，对于 (1le i< K)，若 (i) 为奇数，在布的正面连接 (s_i,s_{i+1})，反之在反面连。若最终正反面的图都联通，则 ({s_i}) 合法。求构造一个最短的合法的 ({s_i})。(Nle 1000, 1le x_i,y_ile 10^9)。
Solution 1
考虑 (N) 个点排成一条直线的情况：显然依次连过去就是答案。
那么怎么对任意的点集可以“依次连过去”呢？
将所有点以 (x) 为第一关键字，按 (y) 为第二关键字排序，最后直接连肯定不相交。复杂度 (O(Nlog N))。
Solution 2
假如说两对点 ((a,b)) 和 ((c,d)) 之间的线段有交怎么办？换成 ((a,c)) 和 ((b,d)) 之后发现欧几里得距离和一定更小。
于是暴力 Kruskal 求出欧几里得最小生成树，然后正反两面都可以用这棵树。最后对这个树求个欧拉序就行了。复杂度 (O(N^2log N))。