斜率优化总结附1：题目浅析

P3195 [HNOI2008]玩具装箱

模板题。

斜率递增，X递增，min/维护上凸壳，单调队列即可。

推式子有一定难度。

上凸壳，单调队列即可。

推式子有一定技巧性。

仍然是上凸壳，单调队列即可。

打好基础，同上。

打好基础，同上。

上凸壳，二分单调队列即可。

二维斜率优化入门。

上凸壳，二分单调队列即可。~~当然也可以WQS二分~~

比较有意思的二维斜率优化。

上凸壳，二分单调队列即可。注意这种二维不是WQS二分。

DFS搜索遍历树，维护栈中的节点的链，即当前节点到根节点这条链，这个链上跑二分。由于需要回退，需要记录单调队列修改的元素。并且需要拆分链，可用树状数组。

上凸壳，树状数组套二分单调队列+回退。

反向推式子比较有技巧性。

接着，WQS二分套上斜率优化的模板题。