金牌导航

777-2 向量问题

求出每个向量出现的时间段，扔到线段树上，对线段树上每个节点维护一个凸包即可，查询时在所有经过的节点上二分一遍，时间复杂度 \(O(n\log^2 n)\)。也可以把询问排序做到单 \(\log\)。

777-3 平面最近点对

将点随机重排，一个一个往里加。设当前答案为 \(ans\)，按 \(ans\times ans\) 分块。加点时只考虑周围 \(9\) 块内的点。不难发现更新的概率约为 \(\frac{i}{i^2}=\frac{1}{i}\)，如果更新答案就暴力重构，时间复杂度 \(O(n)\)。

也可以分治，先求出分治中心两侧的答案的 \(\min\)，记为 \(d\)。随后只取中心线左右距离小于 \(d\) 的点，然后扫一遍它们显然就是对的，因为另一侧只有 \(O(1)\) 个点会更新答案。时间复杂度 \(O(n\log n)\)。

777-4 最小三角形

仿照上一题的分治方法，只取距离不超过 \(\frac{d}{2}\) 的点，显然也是对的。

761-6 树上第K小

对每个节点维护它根链上所有点权的主席树。查询时即可做到 \(O(4\times \log n)\)。

779-1 区间众数

对序列分块，整块预处理，散块暴力加入。为了做到线性空间，我们没法快速查询一个数字 \(x\) 在一个 block 的区间中出现了多少次。因此对每个数值维护一个 pos 数组，对于左侧散块中的一个数字 x，查询 pos[p[x]+ans] 是否仍然在区间内，若是则暴力 ans++，右侧同理，显然总扩展次数是 \(O(B)\) 的，因此时间复杂度是对的。

779-2 区间计数

区间加，区间大于某个数的个数。考虑分块，对块内进行排序，修改时整块打 tag，散块暴力重构。查询时对每个块进行二分，散块暴力。时间复杂度 \(O(n\sqrt n\log n)\)。

779-4 工作评估

对于单个区间，注意到如果没有顶到限制，那么答案是 \(x_0+\sum d_i\)，否则等于 \(f(l,r,+\infty)\)，发现取 \(f(l,r,x_0)=\min(x_0+\sum d_i,f(l,r,+\infty))\) 即可。记 \(a=f(l,r,+\infty),b=\sum d_i\)，那么答案可以表示成 \(\min(a,b+x_0)\)。

考虑如何处理查询。考虑分块，对于完全包含于单个块内的二元组，我们可以除去被偏序的二元组，这样 \(a,b\) 就都有单调性了，可以二分出最优决策点。对于跨块的二元组，我们把所有块扫一边，动态维护目前最大的 \(x\)，然后与当前块的前缀的所有 \((a,b)\) 更新最大值即可。

709-2 铁人两项

考虑如何对固定的起点和终点 \(s,f\) 计数转折点 \(c\)。发现 \(s,t\) 在同一个 bcc 内的时候，\(c\) 只能取该 bcc 内的任意点（因为不能跨过割点）。对于一般情况，建出圆方树，发现 \(c\) 可以取 \(s,t\) 路径经过的所有 bcc 上的点，也就是圆方树上到 \(s\to t\) 路径距离不超过 \(1\) 的圆点。

给圆点赋予 \(-1\) 的点权，方点赋予 \(sz[scc]\) 的点权，那么 \(s,f\) 的贡献就是路径权值之和。枚举每个点会被多少条路径经过即可。

778-5 春节十二响

考虑先求出所有子树的划分方案，那么同一个子树的两个集合不能合并，两个子树的两个集合可以合并。于是可以想出一种贪心策略：让两棵子树，最大值和最大值匹配，次大值和次大值匹配，以此类推。可以归纳的证明这样得到的最优方案偏序其他所有方案，因此正确性显然。

778-7 最短时间

发现我们只需对每个点求出最快多久能将能力值到达路径最大值 \(W\)。考虑 dp，设 \(f_{u,i}\) 表示从 \(u\) 出发，可以在 \(i\) 步之内死，那么能力值的最大值。发现这玩意就是子树内距离 \(u\) 不超过 \(i\) 的所有点的点权最大值。考虑线段树合并，查询形如一次线段树上二分和一次前缀和查询。

Y778-8 森林问题

考虑启发式合并，每次暴力重构较小的子树的主席树和倍增数组。