考虑一下一维情况,似乎只是一个RMQ问题。一维情况下,就是考虑找出一个区间长度固定的一个区间,对应
m
x
−
m
i
n
mx-min
mx−min最小即可. 在二维的情况,考虑枚举该正方形的左上角,需要一个数据结构支持查询二维的一个最大值. 考虑
s
t
st
st表来实现这个功能,因为查询比较多而且是静态的. 然后该
s
t
st
st表是一个二维形式呈现的.
m
x
(
i
,
j
,
k
)
:
mx(i,j,k):
mx(i,j,k):以
(
i
,
j
)
(i,j)
(i,j)为左上角,长度为
2
k
2^k
2k的正方形区域中的最大值.
m
n
(
i
,
j
,
k
)
mn(i,j,k)
mn(i,j,k):以
(
i
,
j
)
(i,j)
(i,j)为左上角,长度为
2
k
2^k
2k正方形区域的最小值.
m
x
(
i
,
j
,
k
)
=
m
a
x
(
m
x
(
i
,
j
,
k
−
1
)
,
m
a
x
(
m
x
(
i
,
j
+
(
1
<
<
k
)
,
k
−
1
)
,
m
x
(
i
+
(
1
<
<
k
)
,
j
,
k
−
1
)
,
m
x
(
i
+
(
1
<
<
k
)
,
j
+
(
1
<
<
k
)
,
k
−
1
)
mx(i,j,k) =max(mx(i,j,k-1),max(mx(i,j+(1
P2216 [HAOI2007]理想的正方形（二维st表）
关注
打赏
查看更多评论
立即登录/注册
微信扫码登录