李超线段树

\text{关于李超线段树的那档事}

包含了6道相关的题和针对李超线段树所涉及的各个板块的题目,有难有易。

P3372 【模板】线段树 1和P3373 【模板】线段树 2为线段树的基本操作。

CF915E Physical Education Lessons和CF803G Periodic RMQ Problem则为线段树动态开点模板。

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包和P3829 [SHOI2012]信用卡凸包为凸包的基本应用。

P5785 [SDOI2012]任务安排是斜率优化dp的经典题目,可以先尝试做P2365 任务安排来熟悉方程式,再尝试加入斜率优化。

其实上面的是为了让题目看起来多一点的。

然后你就会发现李超线段树不就是一个能维护斜率的线段树吗(

所以用李超线段树维护动态凸包和dp什么的也是常态,这一点可以从最后两道题里看出(

所以如果你想练习李超线段树的话可以找个斜率优化dp试一试,比如丝之割。

最后的8道题就是李超线段树的模板和扩展了,熟悉了线段树和斜率后可以很轻松的做出这几道题,已按难度排序。


  1. P3372 - 【模板】线段树 1
  2. P3373 - 【模板】线段树 2
  3. CF915E - Physical Education Lessons
  4. CF803G - Periodic RMQ Problem
  5. P2742 - 【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows
  6. P3829 - [SHOI2012] 信用卡凸包
  7. P2365 - [IOI 2002] 任务安排
  8. P5785 - [SDOI2012] 任务安排
  9. P6047 - 丝之割
  10. P4254 - [JSOI2008] Blue Mary 开公司
  11. P4097 - 【模板】李超线段树 / [HEOI2013] Segment
  12. CF1303G - Sum of Prefix Sums
  13. P4655 - [CEOI 2017] Building Bridges
  14. P4069 - [SDOI2016] 游戏
  15. CF932F - Escape Through Leaf
  16. P5244 - [USACO19FEB] Mowing Mischief P
  17. P5508 - 寻宝