#29. 「COCI 2020.10」3D Histogram

「COCI 2020.10」3D Histogram

题目描述

译自 COCI 2020/2021 Contest #1 T3「3D Histogram」

Malnar 先生(通过电话):听着,我曾在大半夜在 Zagreb 周边贴过一些海报。我遇见了一排栅栏,用不同高度的木板拼成的栅栏,我正想着如何计算我能在这排栅栏上贴上的最大的海报面积。你觉得那会是一道不错的 COCI 题吗?

同事:你在干啥啊?!而且吧,这题也不怎么好。不过是一个用单调队列的套路题罢了,我们甚至在我们的 x 令营里教小学生这些东西呢。

Malnar 先生:如果你稍微改编一下,比如对每个前缀都求一遍之类的,那应该够难了吧。

同事:那就和去年我们的 CERC 资格赛撞题了(H 题)。那题挺难的,难点在 Harbingers 一题(CEOI 2009)采用的技巧上(指在凸包上二分更新 DP),但是现在大家都见过了。

Malnar 先生:你确定我们真的束手无策了吗?

同事:我觉得我们已经出完了所有直方图类型的题目了。COCI 2010/2011 的 Tabovi,COCI 2015/2016 的 Poplava,COCI 2017/2018 的 Krov,2018 年的 IOI 选拔赛的 Histogram…… 你懂的。

Malnar 先生:如果直方图是三维的呢?

同事:嗯……

给定一张三维的直方图,包含 nn 个接连排列的块。第 ii 个块有 11 米宽,aia_i 米高,bib_i 米长。换句话说,从前面看,就像是每组高度分别为 a1,a2,,ana_1, a_2, \ldots , a_n 的直方图,从上面看,就像是每组高度分别为 b1,b2,,bnb_1, b_2, \ldots , b_n 的直方图。

请求出三维直方图中能放下的最大体积的长方体。长方体的各个面需要和组成三维直方图的所有块的各个面平行。

输入格式

第一行一个正整数 nn
接下来 nn 行,第 ii 行两个正整数 ai,bia_i, b_i

输出格式

输出最大的体积的立方米数。

样例 1

5
5 3
4 4
2 1
3 2
1 5
24

下图显示了样例 1 的三维直方图。最大体积的长方体使用了前两个块的一部分,有 22 米宽,44 米高,33 米长。它的体积为 243=242 \cdot 4 \cdot 3 = 24 立方米。

6
3 1
2 1
2 2
2 3
1 1
2 2
8
5
15 19
5 6
1 13
3 7
1 2
285

数据范围与提示

子任务编号 分值 特殊限制
11 1818 1n20001 \le n \le 2000
22 8282 1n2×1051 \le n \le 2 \times {10}^5

译者:PinkRabbit