BZOJ 1047 – 理想的正方形

题目链接:BZOJ 1047

这是一个典型的静态二维RMQ问题。

我们首先对于每一行使用单调队列维护第$i$行以第$j$列为结尾的长度为$n$的$1\times n$的序列的最值,这里记为rMin和rMax;然后对于rMin和rMax两个二维数组,再次使用单调队列维护第$j$列以第$i$行为结尾的的长度为$n$的$n\times 1$序列的最值,记为cMin和cMax,此时,cMin和cMax里的第$i$行第$j$个元素代表以这个位置为右下角的$n \times n$矩阵的最值。

渐进时间复杂度$O(ab)$。

 

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 典型二维RMQ,具体解法见我的上一篇博文BZOJ 1047 – 理想的正方形(题解)。 […]