这次我们讨论一下有关区间中的值的问题。如果你只想看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原创，转载请注明出处）
