Codeforces 678 F – Lena and Queries (分治,线段树,维护凸包)

n个询问,三种操作:
1. 在集合中加入点(x, y);
2. 在集合中删除操作i加入的点;
3. 在集合中询问使得qx + y最大的点

如何不考虑增加和删除操作,考虑询问,不妨令z = qx + y那么y = -qx + z,也就是找出一个点(x, y)使得经过(x, y)的直线y – qx + z在y轴上的截距最大,会发现最优解存在于这些点构成的凸包上,因为对点集根据x、y排序,然后用Grahan跑出凸包,于是只要在凸包上三分即可。
现在来考虑如果有添加删除操作该如何搞,任何一个点都存在可行的询问范围,我们将询问的每个时间点建立线段树,对于添加的点搞出其可行范围插入到线段树上,这样线段树每个节点上的点集就代表此区间有效的点集,当插入结束对整颗线段树分治,对于线段树每个节点上的点集搞一个凸包,对于每个可行区间的询问更新最大值。总体复杂度是O(nlognlogn)

 

 

LEAVE A COMMENT