这题也太毒瘤了,警示后人

P4655 [CEOI2017] Building Bridges

ivyjiao @ 2024-11-09 17:57:35

关于 LCT(Li Chao Tree)写法:

  • 如果你是从 LCT 板子过来的,注意这题插入的是直线,不是线段!
  • 不要在 query 里写 return min(f(w,h[v]),min(query(ls,l,mid,v),query(rs,mid+1,r,v))); 之类的东西,会 T 飞,正确写法是 return min(f(w,h[v]),h[v]<=mid? query(ls,l,mid,v):query(rs,mid+1,r,v));
  • 注意线段树递归条件别写反了。
  • 斜率别递归错了,带 h[i] 的才是斜率,h[j] 不是。
  • 系数 -2 只能给 k x 中的一个!

|