Day1

100+100+70+60，rank 5。

A

对 \(\{a_n\}\) 排序后，最优的方案一定是选一个前缀，于是二分一下即可。

B

钦定 \(1\) 为根，对于一条非树边 \((u_i,v_i)\)，在树上 \(u_i\leadsto v_i\) 的路径上的所有边的边权都需要小于这条非树边的边权。根据这个，我们可以按照边的编号从小到大贪心。用并查集维护某个点 \(u\) 的祖先中，深度最小的、还未确定边权的 \((x,\mathrm{fa}_x)\) 即可。

时间复杂度 \(O(n\log n)\)。

C

因为写完这题以后没时间对拍了，所以写挂了。

设 \(f_i\) 表示：只考虑所有 \(r_j\le i\) 的区间 \([l_j,r_j]\)，让这些区间形成的连通块大小不超过 \(k\) 的最小代价。枚举一个 \(x\le i\)，我们计算使得 \([x,i]\) 中的区间形成一个连通块的代价 \(\operatorname{cost}(x,i)\)，转移就是 \(f_i=\min_{1\le x\le i}\{f_{x-1}+\operatorname{cost}(x,i)\}\)。这个代价分为两部分：

• 设完全被 \([x,i]\) 包含的区间有 \(c\) 个，若 \(c>k\)，我们需要删除其中代价最小的 \((c-k)\) 个区间；
• 我们需要将 \(l_j\in [1,x)\land r_j\in [x,i]\) 的区间全部删除。

通过一些简单的处理，可以做到 \(O(n^2\log n)\)。

D

洛谷 P6106 弱化版。

我的 60 分做法

对于测试点 \(1,2,3,4,7,8\)，暴力拆出来的矩形个数 \(c\) 不超过 \(2.5\times 10^8\)。也就是说，我们需要支持 \(c\) 次矩形加，加完以后有 \(q\) 次单点查询。用分块平衡一下，可以做到 \(O(c+q\sqrt{V})\)。

但是直接这样做会爆空间。用莫队二次离线中的优化空间的方法，我们只记录线段从哪里开始移动、移动了多少个位置、移动的方向，在扫描线的过程中用 std::forward_list 维护所有存在的线段。这样我们只需要记录 \(O(m)\) 个操作，空间复杂度 \(O(n+m+q)\)。

正解

对于正着的移动和斜着的移动分别考虑。正着的、斜着的移动分别有两种，我们分别只考虑其中的一种，剩下的一种通过旋转坐标轴来处理。仍然做扫描线并维护差分数组。

• 对于竖向的移动，在差分数组上表现为区间加。
• 对于斜向的移动，斜着做扫描线。

代码不可能写。