[BZOJ 2300] [HAOI 2011] 防线修建

题意:只有删点与查询操作,动态地维护一个上凸包的周长。

首先可以把题目离线化,倒转时间轴,则可以把题目转换成动态加点并维护凸包周长。

维护的实现可以采用平衡树(set)来做:在树上找到当前点的前驱与后继点(按 xy 坐标排序),然后判断是否符合凸包条件,若不满足则不断删去前驱后继并更新周长。

Note:

  1. 计算初始答案前就应当构建出一个凸包(可以用后面的方法做)。
  2. 这题 cin / cout 非常慢,全改成 scanf / printf 后快了 1s+

Reference:

https://erjiaqing.github.io/2014/04/14/bzoj2300/

代码如下:

继续阅读[BZOJ 2300] [HAOI 2011] 防线修建