2019牛客多校第二场H – Second Large Rectangle

题目链接:2019牛客多校第二场H

动态维护第$i$行的每一个元素$s_{i,j}$,向上最大能到达的高度$h_j$,向左能到达的最远点$l_j$,向右能到达的最远点$r_j$,满足$l_j$和$r_j$的$h$值都是大于等于$h_j$的。

那么我们知道最大值是

$$ \max_{i = 1}^{n} \max_{j = 1}^{m} h_j \times (r_j – l_j + 1) $$

那么我们只要在$h_j \times (r_j – l_j + 1)$的基础上减去一行或者一列,以及$h_j \times (r_j – l_j + 1)$本身都存起来,排序去重后取第二个就是全局第二大。

渐进时间复杂度$O(n^2 \log n)$。

【吐槽:去重居然卡set】

 

说点什么

avatar
50
  Subscribe  
提醒