hdu5127 Dogs' Candies CDQ分治 动态凸包

• 传送门

• 题意
  有三种操作

  • 加入一个二元组((x,y))
  • 删除一个二元组((x,y))
  • 给出一个二元组((a,b))，问(ax+by)的最大值

• 题解
  (z=ax+by Rightarrow y=-frac{b}{a}x+frac{z}{b})
  分(b)的符号讨论，分别维护上下凸壳。
  对于删除操作，将右边的序列反过来之后转化为没有删除操作的询问，用经典的(mathrm{CDQ})分治完成.

• notice
  简直恶心，转化序列的时候恶心死了。

• code