前言

单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式,在一个点可以更新一个范围的时候可以发挥很大作用。

记得当年NOIp2017我考PJ(那年的T4考到了单调队列),当时还不会,在考后听教练讲了一遍之后仍旧处于懵逼状态,大概1个月前照着题解打了一遍,但是到了现在已经忘得差不多了QwQ,于是写了一遍优化过的多重背包来练练手。