给出一个长度为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
Darkmaster说:“这题水吧?水了就得给我AC了看看,呵呵!”
输入格式
第一行两个正整数N,M。
第二行N个数,表示序列A1,A2,...,AN。
紧着的M行,每行三个正整数i,j,k(k≤j-i+1),表示
询问Ai...Aj中第k小的数等于多少。
输出格式
共输出M行,第i行输出第i个询问的答案。
程序代码
program least;
var a,b:array[1..10000] of longint;
i,j,m,n,m1,m2,m3,t:integer;
f:longint;
procedure qsort(head,tail:longint);
var x,i,j:integer;
begin
x:=b[head];
i:=head;
j:=tail;
while i<j do
begin
while(i<j) and (b[j]>=x) do j:=j-1;
b[i]:=b[j];
while(i<j) and (b[i]<=x) do i:=i+1;
b[j]:=b[i];
end;
b[i]:=x;
if head<i-1 then qsort(head,i-1);
if i+1<tail then qsort(i+1,tail);
end;
begin
readln(n,m);
for i:=1 to n do read(a[i]);
readln;
for i:=1 to m do
begin
readln(m1,m2,m3);
t:=0;
for j:=m1 to m2 do
begin
t:=t+1;
b[t]:=a[j];
end;
qsort(1,t);
writeln(b[m3]);
end;
end.
样例数据过了 但是WA:0 -,- Who can help me?