944ms
type
  node=record
    x,y,l,r,mid:longint;
  end;
var
  tree:array [0..400000] of node;
  a:array [1..100001] of longint;
  b,c:array [0..20,1..100001] of longint;
  n,m,tot:longint;
procedure init;
var
  i:longint;
begin
  tot:=0;
  readln(n,m);
  for i:=1 to n do
  begin
    read(a[i]);
    b[0,i]:=a[i];
  end;
  readln;
end;
procedure qsort(x,y:longint);
var
  p,q,mid,t:longint;
begin
  p:=x;
  q:=y;
  mid:=a[(x+y) div 2];
  repeat
    while a[x]<mid do inc(x);
    while a[y]>mid do dec(y);
    if x<=y then
    begin
      t:=a[x];
      a[x]:=a[y];
      a[y]:=t;
      inc(x);
      dec(y);
    end;
  until x>y;
  if p<y then qsort(p,y);
  if x<q then qsort(x,q);
end;
procedure buildtree(x,y,dep:longint);
var
  i,lt,rt,j,mid:longint;
begin
  inc(tot);
  i:=tot;
  tree[i].x:=x; tree[i].y:=y; tree[i].mid:=(x+y) div 2;
  if x=y then exit;
  lt:=x-1; rt:=tree[i].mid; mid:=a[(x+y) div 2];
  for j:=x to y do
  if (b[dep-1,j]<=mid) and (lt<tree[i].mid) then
  begin
    inc(lt); b[dep,lt]:=b[dep-1,j];
    if j=x then c[dep,j]:=1
    else c[dep,j]:=c[dep,j-1]+1;
  end
  else
  begin
    inc(rt); b[dep,rt]:=b[dep-1,j];
    if j=x then c[dep,j]:=0
    else c[dep,j]:=c[dep,j-1];
  end;
  tree[i].l:=tot+1;
  buildtree(x,(x+y) div 2,dep+1);
  tree[i].r:=tot+1;
  buildtree((x+y) div 2+1,y,dep+1);
end;
function count(p,x,y,k,dep:longint):longint;
var
  mid,ls,rs:longint;
begin
  if (tree[p].x=x) and (tree[p].y=y) then exit(a[x+k-1]);
  if tree[p].x=x then ls:=0 else ls:=c[dep,x-1]; rs:=c[dep,y];
  if k<=rs-ls then exit(count(tree[p].l,tree[p].x+ls,tree[p].x+rs-1,k,dep+1))
  else exit(count(tree[p].r,tree[p].mid+(x-tree[p].x+1-ls),tree[p].mid+(y-tree[p].x+1-rs),k-rs+ls,dep+1));
end;
procedure main;
var
  i,j,x,y,z:longint;
begin
  for i:=1 to m do
  begin
    readln(x,y,z);
    writeln(count(1,x,y,z,1));
  end;
end;
begin
  while not eof do
  begin
    init;
    qsort(1,n);
    buildtree(1,n,1);
    main;
  end;
end.

• Re:pascal 题解 (124) YvesChan 2014-01-19 11:19:29