题意:只有删点与查询操作,动态地维护一个上凸包的周长。
首先可以把题目离线化,倒转时间轴,则可以把题目转换成动态加点并维护凸包周长。
维护的实现可以采用平衡树(set)来做:在树上找到当前点的前驱与后继点(按 xy 坐标排序),然后判断是否符合凸包条件,若不满足则不断删去前驱后继并更新周长。
Note:
- 计算初始答案前就应当构建出一个凸包(可以用后面的方法做)。
- 这题 cin / cout 非常慢,全改成 scanf / printf 后快了 1s+
Reference:
https://erjiaqing.github.io/2014/04/14/bzoj2300/
代码如下: