包含了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道题就是李超线段树的模板和扩展了,熟悉了线段树和斜率后可以很轻松的做出这几道题,已按难度排序。