?? ? ?這次我們討論一下有關(guān)區(qū)間中的值的問題。如果你只想看RMQ，請?zhí)^下面這幾段，在第一段代碼的后面有詳細(xì)的講解。
?? ? ?在競賽中，我們經(jīng)常遇到最值問題。但是出題者往往給我們出一些這樣的題目，讓我們找到第K優(yōu)解，而不是最優(yōu)，比如K小生成樹、K優(yōu)背包等等。這篇文章主要介紹另一個(gè)“K問題“，區(qū)間第K大值。
?? ? ?區(qū)間第K大值的題意很明確，對(duì)于一個(gè)區(qū)間，找到其中第K大的一個(gè)數(shù)輸出。這個(gè)問題可以用O（n 2 ）的算法枚舉，但是當(dāng)區(qū)間很大的時(shí)候這種方法就會(huì)很費(fèi)時(shí)。我們還可以將區(qū)間內(nèi)的序列排序，直接輸出a[k+l-1]（l是區(qū)間左端點(diǎn)）即可。
?? ? ?我們知道，快排的原理是找到一個(gè)標(biāo)準(zhǔn)點(diǎn)，然后進(jìn)行交換、分組，直到它的左邊（以遞增為例）都比它小，右邊都比它大為止。但是結(jié)合這道題來說，每進(jìn)行一遍分 ? ? ?組，第K大值就會(huì)確定的位于其中一組，或者就是那個(gè)標(biāo)準(zhǔn)點(diǎn)。然后我們只用將有第K大值的那個(gè)組再進(jìn)行分組、查找（不是標(biāo)準(zhǔn)點(diǎn)），或者直接輸出標(biāo)準(zhǔn)點(diǎn)（正好是標(biāo)準(zhǔn)點(diǎn)）。這樣，我們就可以以少于1/2的操作找到我們想要的數(shù)。
?? ? ?對(duì)于多次詢問，我們要保留下原始序列，以免之后再尋找時(shí)出現(xiàn)錯(cuò)誤。
?? ? ?給出一道比較水的題，大家可以試一下~
?
?
【題目描述】（rqnoj350）
給出一個(gè)長度為N的序列A1,A2,A3,...,AN，其中每項(xiàng)都是
小于10
^
5的自然數(shù)。
現(xiàn)在有M個(gè)詢問，每個(gè)詢問都是Ai...Aj中第k小的數(shù)等
于多少。
數(shù)據(jù)范圍：
在60
%
的數(shù)據(jù)中，
1
≤N≤
1000
，
1
≤M≤
1000
在100
%
的數(shù)據(jù)中，
1
≤N≤
10000
,
1
≤M≤
2000
【輸入格式】
第一行兩個(gè)正整數(shù)N，M。
第二行N個(gè)數(shù)，表示序列A1,A2,...,AN。
緊著的M行，每行三個(gè)正整數(shù)i,j,k(k≤j
-
i
+
1
)，表示
詢問Ai...Aj中第k小的數(shù)等于多少。
【輸出格式】
共輸出M行，第i行輸出第i個(gè)詢問的答案。
【樣例輸入】
4
3
4
1
2
3
1
3
1
2
4
3
1
4
4
【樣例輸出】
1
3
4
?
?
?
?? ? ?分析就不用了，直接貼代碼吧~
?
?? ? ?參考代碼：
?
1
program
knum;
2
var
3
a,t:
array
[
1
..
3000000
]
of
longint;
4
n,k,i,m,l,r:longint;
5
function
sort(l,r,k:longint):longint;
//
改編的快排
6
var
7
i,j,x,y:longint;
8
begin
9
if
l
=
r
then
exit(a[l]);
//
兩指針可能重合。這條語句可以減少時(shí)間消耗
10
i:
=
l;
11
j:
=
r;
12
x:
=
a[(i
+
j) shr
1
];
13
repeat
14
while
a[i]
<
x
do
inc(i);
15
while
a[j]
>
x
do
dec(j);
16
if
i
<=
j
then
17
begin
18
y:
=
a[i];
19
a[i]:
=
a[j];
20
a[j]:
=
y;
21
inc(i);
22
dec(j);
23
end
;
24
until
i
>
j;
25
if
(k
>=
i)
then
exit(sort(i,r,k));
//
①
26
if
(k
<=
j)
then
exit(sort(l,j,k));
27
exit(x);
//
如果是標(biāo)準(zhǔn)點(diǎn)就直接輸出
28
end
;
29
begin
30
readln(n,m);
31
for
i:
=
1
to
n
do
32
read(t[i]);
33
for
i:
=
1
to
m
do
34
begin
35
a:
=
t;
//
保留原序列，對(duì)“鏡子“序列進(jìn)行操作
36
readln(l,r,k);
37
writeln(sort(l,r,l
+
k
-
1
));
//
②
38
end
39
end
.
40
P．S．① a）因?yàn)閗∈[l，r]，所以不用判斷i是否小于r；
41
b）由于i
>
j，這條語句和以下兩條語句沒有交集。
42
②一定是l
+
k
-
1
，因?yàn)槭菂^(qū)間的第K小值，所以尋找k肯定不對(duì)。
?
?
?
?
?? ? ?當(dāng)然，對(duì)于區(qū)間最值問題（RMQ），這種方法也能解決。為什么還要有求區(qū)間最值（RMQ）的偉大的ST算法呢？
?? ? ?有句頗有哲理的話說得好，存在即合理。師傅告訴我，上面改裝快排的時(shí)間效率是O（nm），所以當(dāng)m很大時(shí)，這種方法就無法快速出解了。這時(shí)，強(qiáng)大的ST（Sparse Table）算法應(yīng)運(yùn)而生（為了劇情需要^_^）！ST算法可以在O（nlogn）的時(shí)間中構(gòu)造一個(gè)強(qiáng)大的數(shù)組，然后只用O（1）的時(shí)間就能針對(duì)每次詢問找到解。
?? ? ?這個(gè)強(qiáng)大的數(shù)組的名字叫做f[i,j]（好俗…），表示從區(qū)間的第i位開始，長度為2 i 的區(qū)間的最大值（姑且以求區(qū)間最大值為例）。這句話聽起來很玄乎，可是怎么構(gòu)造這個(gè)數(shù)組呢？
?? ? ?我們先把f[i,0]賦成讀入的第i個(gè)數(shù)（也就是以i為起點(diǎn)，長度為2 0 =1的區(qū)間內(nèi)的最值）。因?yàn)閖表示長度為2 j ，所以我們可以把整個(gè)f[i,j]表示的區(qū)間劃分[i,j-1]和[i+2 (j-1) ,j-1]兩個(gè)區(qū)間，然后調(diào)用f中存儲(chǔ)的兩個(gè)區(qū)間中的最大值，取其中較大的那個(gè)就行！
?? ? ?有的人可能疑惑，f[i,j]劃分的兩個(gè)空間的最值是什么時(shí)候求出來的呢？別忘了我們的初始化。有了j=0時(shí)的最值，j=1時(shí)的最值就很好求了。顯然，j的最大值是trunc（log 2 n），這樣，我們只要讓j從1循環(huán)到trunc（log 2 n），把目的區(qū)間由小逐漸擴(kuò)大，之后就能隨意地調(diào)用原來的解啦！整個(gè)過程循環(huán)完以后，任何一個(gè)長度為2 j 的區(qū)間的最值就全部求出來了。
?? ? ?長度為2 j 區(qū)間的最值是有了，但是如果詢問的區(qū)間的長度2 j 和2 j+1 之間呢？舉一個(gè)例子。假設(shè)原序列是4 2 8 6 1 7 3，求3到7這個(gè)區(qū)間的最大值。
?? ? ?尋找的時(shí)候就只用尋找圖中的兩個(gè)區(qū)間的最大值即可，這樣整個(gè)區(qū)間就都能夠被覆蓋，即使交集也不會(huì)影響結(jié)果。
?? ? ?另外一道比較水的題，大家也可以試試~
?
【題目描述】（tyvj p1038）
老管家是一個(gè)聰明能干的人。他為財(cái)主工作了整整10年，財(cái)主為了讓自已賬目更加清楚。要求管家每天
記k次賬，
由
于
管家聰明能干，因而管家總是讓財(cái)主十分滿意。但是由于一些人的挑撥，財(cái)主還是對(duì)管家產(chǎn)生
了懷疑。于是他決定
用
一
種特別的方法來判斷管家的忠誠，他把每次的賬目按1，
2
，
3
…編號(hào)，然后不定時(shí)的
問管家問題，問題是這樣的：在
a
到
b號(hào)賬中最少的一筆是多少？為了讓管家沒時(shí)間作假他總是一次問多個(gè)問題。
【輸入格式】
輸入中第一行有兩個(gè)數(shù)m,n表示有m(m
<=
100000
)筆賬,n表示有n個(gè)問題，n
<=
100000
。
第二行為m個(gè)數(shù),分別是賬目的錢數(shù)
后面n行分別是n個(gè)問題,每行有2個(gè)數(shù)字說明開始結(jié)束的賬目編號(hào)。
【輸出格式】
輸出文件中為每個(gè)問題的答案。具體查看樣例。
【樣例輸入】
10
3
1
2
3
4
5
6
7
8
9
10
2
7
3
9
1
10
【樣例輸出】
2
3
1
?
?
?? ? ?參考代碼：
?
1
program
ST;
2
var
3
f:
array
[
0
..
100000
,
0
..
19
]
of
longint;
//
j的最大值是trunc（log2n），計(jì)算器算一下
4
i,j,n,m,l,r:longint;
5
function
min(x,y:longint):longint;
6
begin
7
if
x
<
y
then
exit(x)
8
else
exit(y);
9
end
;
10
begin
11
readln(n,m);
12
for
i:
=
1
to
n
do
//
初始化f數(shù)組
13
read(f[i,
0
]);
14
for
j:
=
1
to
trunc(ln(n)
/
ln(
2
))
do
//
循環(huán)j的長度
15
for
i:
=
1
to
n
-
1
<<
j
+
1
do
//
i的最大值n
-
1
<<
j
+
1
16
f[i,j]:
=
min(f[i,j
-
1
],f[i
+
1
<<
(j
-
1
),j
-
1
]);
//
動(dòng)態(tài)規(guī)劃更新f數(shù)組，注意兩個(gè)區(qū)間
17
for
i:
=
1
to
m
do
18
begin
19
readln(l,r);
20
j:
=
trunc(ln(r
-
l
+
1
)
/
ln(
2
));
//
j就是圖示中的k
21
write(min(f[l,j],f[r
-
1
<<
j
+
1
,j]),
'
'
);
//
跟圖中一樣
22
end
;
23
end
.
?
?
?? ? ?終于寫完了~累死了…有什么不對(duì)的地方和說得不明白的地方歡迎大家提出！我一定盡快改正！
（Saltless原創(chuàng)，轉(zhuǎn)載請注明出處）
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
