XXI Open Cup GP of Korea

A. Advertisement Matching

从大到小排序后显然可以贪心，合法条件是所有前缀和都有 $a\geq b$ 。

用线段树维护 a 和 b 的差，每次单点修改查询前缀和最小值。

~~迫真 Cactus。~~

考虑类似 AGC028F 的做法，找到对于每个左边的点，右边能到达的上界和下界。这个上下界中所有能被任意左侧点到达的点都能被这个点到达。

“能被左侧任意点到达”就是求旋转 180 度以后右边能到达的上下界，没什么区别。

由于这个图的性质，任意两行或任意两列的墙都是子集关系。那么如果一个左侧的点无法走到最右侧，那么一定存在一些墙构成一个 L 型（最多只会拐一次弯）。并且一个点如果能到达右侧，那么上下界分别是第一行全没墙的和第一行全是墙的（下界多往下一点没有关系，因为都是墙最后也不会统计进答案里。

然后就可一从下往上扫描线。时间复杂度 $O(n \log n)$ 。

考虑如何构造一个边双。

维护一个点集 $S$，初始包含 1 号点。每次从 $S$ 中选出 $u,v$ ，然后选一条 $u \to x_1 \to x_2 \to ... \to x_k \to v$ 的路径。

根据这个构造方法就有一个 $O(2^nn^3)$ 的 dp，可以通过，需要注意细节。

先找出最大生成树，然后每条非树边的权值必须为树上对应路径的最小值。如果有多个连通块，不同连通块之间连 1 的边。

先判断是否每条非树边都符合要求，再用并查集求答案即可。

区间图经典套路。一个图是链当且仅当：

第一个条件用 lct，第二个条件用 set 可以求出对于每个右端点左端点的下界。第三个条件可以通过线段树上区间加减区间最小值个数实现。

生成树其实是链，本质上是选出两组不相交的区间使得权值和最大。

显然的费用流模型，流量为 2。原始对偶，把第一次 SPFA 改为 DAG 上 dp 即可。时间复杂度 $O(m \log m)$ 。

dp 套 dp 板子。

由于至少要合并一次，所以如果可以通过先变 0 再在最后一次中把 0 一起干掉的做法，删去一个数。因此答案是可以二分的。

判定问题是简单的。

经典结论。带权重心一定在 dfn 序列的带权中点到根的路径上。树剖二分即可。

签到题。

签到题。

单个矩形 $\iff$ 凸 $\iff$ 没有凹点。

发现一次切割会把那两个端点（如果是凹的）变凸，也就是每次切割干掉一个或两个凹点。那么就相当于要最大化两个凹点的操作的数量。

若干次干掉两个的操作能进行当且仅当他们无交。也就是找出最大独立集。

发现所有竖着的线段可以看作点，横着的线段可以看作区间，因此可以贪心求出最大匹配。