线段树优化凸壳

Lena and Queries

题目链接:http://codeforces.com/contest/678/problem/F

三种操作,1.插入一个点(x,y) 2.删除之前第i个操作插入的点 3.给一个q,询问在已有点中qx+y最大是多少

如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立,所以不能cdq分治。

但是可以用上一次线段树优化建图一样的技巧,按时间来看,因为每个点的存在是一段区间,那么就可以用线段树拆成log个区间,然后把点“打”在上面(加进vector),最后对于线段树上每个区间,做凸壳然后询问就行了。每个询问会被问log次,所以时间复杂度粗略算有\(O(nlog^2n)\)。