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