金牌导航

777-2 向量问题

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

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

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

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

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