二维直方图最大矩形是一个特别经典的问题，利用单调栈即可在 $O(n)$ 复杂度解决，那么三维的呢？你会发现无从下手（暴力方法就不说了，没啥意思，最多就是多线程处理）。此题跨度之长，因此需要补的东西之多，值得单独写一篇博文。

时间线

  • 2021-4-13 看到
  • 2021-4-15 想做（然后即使看了题解依然不会）
  • 2021-4-16 询问好友 SevenDawns 才知道此题问原题：COCI2020-2021#1，并给了他同学写的题解（依然看不懂）
  • 2021-4-18 在洛谷里其中唯一的一篇题解用到了 SDOI2014 向量集 的技术。而此题 Kczno1 的做法 牵扯到了线段树优化，凸包优化。于是想在这里 学习凸包优化 DP（后来才知道这就是斜率优化 DP），但是又牵扯到 线段树优化 DP 于是乎
  • 2021-5-4 在 OI-wiki 学习一下 可持续化线段树，详见 可持久化算法，学完之后发现权值线段树问题可以用整体二分来离线处理，详见 整体二分
  • 2021-5-7 开始动手 SDOI2014 向量集，晚上的时候，想想还是算了~
  • 2021-5-7 发现原题不依赖 向量集 这题，因为原题中斜率是单调的，所以直接用斜率优化 DP 就可以啦，而且时间和代码复杂度骤降！但还是好恶心，算了算了，以后再说吧！

太菜了