AC. 梦想

frank_c1

[BZOJ 4311] 向量

发布于2017年01月22日 | 暂无评论 | 526阅读 | 分治

题意简述

维护一个向量集合,支持以下操作:

1. 插入一个向量(x,y)

2. 删除插入的第i个向量。

3. 查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0。

1 \le n \le 200000, 1 \le x,y \le 10^6

算法讨论

考虑每一个向量,如果在时间轴上看,存在时间都对应一段区间。

对时间分治,运用线段树的思想把向量定位到O(\log n)个结点上,与此同时将询问下传更新答案即可。

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