20251107

考试开始想了半个小时，后面又追加了半个多小时，但还是没想出来。

AI题解没看懂，用户题解yyds。

说实话，在要求最高位最大的时候从低位到高位枚举不容易想到，因为高位的价值远大于低位。

但题解使用一种类似反悔的做法，在可以加入高位的时候，把低位的那些反悔掉（从堆里面清出去），这是不常见的。

感觉这个trick会很有用，就写这了。

这个trick可以想到李超线段树，毕竟都有直线了。

这样这道题就变成了李超线段树的模板题。离线下来，扫一遍前缀，扫一遍后缀就做完了。

写了1h,调了0.5h。李超线段树本身没错，前面的坐标轴平移写错了。

被 CF *3100 吓哭了

观察到测试点8专门给个 $n \le 2000,m \le 20$ 肯定跟 $2^m$ 有点关系,就想到状压了。

发现按照剩余时间可能能多打点表创更多数据。就写打表程序。

思路并不复杂，细节多得要死，写了1h才写完。一测样例错了。

这时候时间不太多了，赶紧去补 T1 暴力。然后T1暴力 $\dfrac{2^n\times n^2}{8}$ 没创过 $n \le 20$。但是没有更多时间了。我赶紧回来调代码，无果。最后把错的表拼了个样例交上去了。

我是不是该先写个 $O(2^{nm})$ 来着？

发现操作2与【单调队列/滑动窗口】有大大的联系。思考数据结构维护单调队列，偏到哪里去了都不知道。

题解只看懂 $O(n\log^2 n)$，单 $\log$ 正解神秘。