Program Pku2761;

Type
  Ttree=^Tt;
  Tt=record
       v,k,p,s:longint;
       l,r,f:Ttree;
     end;

Var
  ans:array[1..500]of longint;
  p:array[1..1000]of longint;
  q:array[0..500,1..4]of longint;
  t,v:Ttree;
  n,m:longint;

Procedure Initialize;
Var
  i,j:longint;
Begin
  readln(n,m);
  for i:=1 to n do
    read(p[i]);
  for i:=1 to m do
  begin
    readln(q[i,1],q[i,2],q[i,3]);
    q[i,4]:=i;
  end;
End;

Procedure Sort(l,r:longint);
Var
  i,j,k,h:longint;
Begin
  i:=l;
  j:=r;
  k:=q[(i+j) div 2,1];
  h:=q[(i+j) div 2,2];
  while i<=j do
  begin
    while (q[i,1]<k) or ((q[i,1]=k) and (q[i,2]<h)) do inc(i);
    while (q[j,1]>k) or ((q[j,1]=k) and (q[j,2]>h)) do dec(j);
    if i<=j then
    begin
      q[0]:=q[i];
      q[i]:=q[j];
      q[j]:=q[0];
      inc(i);
      dec(j);
    end;
  end;
  if l<j then Sort(l,j);
  if i<r then Sort(i,r);
End;

Procedure Ins(t:Ttree);
Begin
  if t^.v>v^.v then
  begin
    if t^.l<>nil then Ins(t^.l)
    else begin
      new(t^.l);
      t^.l:=v;
      t^.l^.f:=t;
    end;
  end
  else begin
    if t^.r<>nil then Ins(t^.r)
    else begin
      new(t^.r);
      t^.r:=v;
      t^.r^.f:=t;
    end;
  end;
  t^.s:=1;
  if t^.l<>nil then t^.s:=t^.s+t^.l^.s;
  if t^.r<>nil then t^.s:=t^.s+t^.r^.s;
End;

Procedure Find(t:Ttree;j:longint;var v:TTree);
Begin
  if t=nil then begin
                  v:=nil;
                  exit;
                end;
  if (t^.v=p[j]) and (t^.p=j) then
  begin
    v:=t;
    exit;
  end;
  if t^.v>p[j] then Find(t^.l,j,v);
  if t^.v<p[j] then Find(t^.r,j,v);
  if t^.v=p[j] then
  begin
    Find(t^.l,j,v);
    if v<>nil then exit;
    Find(t^.r,j,v);
  end;
End;

Procedure Right(g,f,ff:Ttree);
Begin
  g^.r^.f:=f;
  if f<>nil then f^.l:=g^.r;
  g^.r:=f;
  f^.f:=g;
  g^.f:=ff;
  if ff<>nil then
    if f=ff^.l then ff^.l:=g
               else ff^.r:=g;
  f^.s:=1;
  if f^.l<>nil then f^.s:=f^.s+f^.l^.s;
  if f^.r<>nil then f^.s:=f^.s+f^.r^.s;
  g^.s:=1;
  if g^.l<>nil then g^.s:=g^.s+g^.l^.s;
  if g^.r<>nil then g^.s:=g^.s+g^.r^.s;
End;

Procedure Left(g,f,ff:Ttree);
Begin
  g^.l^.f:=f;
  if f<>nil then f^.r:=g^.l;
  g^.l:=f;
  f^.f:=g;
  g^.f:=ff;
  if ff<>nil then
    if f=ff^.l then ff^.l:=g
               else ff^.r:=g;
  f^.s:=1;
  if f^.l<>nil then f^.s:=f^.s+f^.l^.s;
  if f^.r<>nil then f^.s:=f^.s+f^.r^.s;
  g^.s:=1;
  if g^.l<>nil then g^.s:=g^.s+g^.l^.s;
  if g^.r<>nil then g^.s:=g^.s+g^.r^.s;
End;

Procedure Turn(g:Ttree);
Begin
  while (g^.f<>nil) and (g^.k>g^.f^.k) do
  begin
    if g=g^.f^.l then Right(g,g^.f,g^.f^.f)
                 else Left(g,g^.f,g^.f^.f);
  end;
  if g^.f=nil then t:=g;
End;

Procedure Del(j:longint);
Var
  f:Ttree;
Begin
  Find(t,j,v);
  f:=v^.f;
  f^.s:=f^.s-1;
  if (v^.l=nil) and (v^.r=nil) then
  begin
    if f<>nil then
      if f^.l=v then f^.l:=nil
                else f^.r:=nil
    else t:=nil;
    exit;
  end;
  if v^.l=nil then
  begin
    if f<>nil then
      if f^.l=v then f^.l:=v^.r
                else f^.r:=v^.r
    else t:=v^.r;
    v^.r^.f:=f;
    t^.f:=nil;
    exit;
  end;
  if v^.r=nil then
  begin
    if f<>nil then
      if f^.l=v then f^.l:=v^.l
                else f^.r:=v^.l
    else t:=v^.l;
    v^.l^.f:=f;
    t^.f:=nil;
    exit;
  end;
  if f<>nil then
  begin
    v^.l^.f:=f;
    if f^.l=v then
    begin
      f^.l:=v^.l;
      v:=v^.r;
      Ins(f^.l);
    end
    else begin
      f^.r:=v^.l;
      v:=v^.r;
      Ins(f^.r);
    end;
  end
  else begin
    t:=v^.l;
    t^.f:=nil;
    v:=v^.r;
    Ins(t);
  end;
  Turn(v);
End;

Procedure Print(t:Ttree;i,j:longint);
Var
  k:longint;
Begin
  if t^.l<>nil then k:=t^.l^.s
               else k:=0;
  if i=k+1 then
  begin
    ans[q[j,4]]:=t^.v;
    exit;
  end;
  if i<k+1 then Print(t^.l,i,j)
           else Print(t^.r,i-k-1,j);
End;

Procedure Main;
Var
  i,j,h,tt:longint;
Begin
  randomize;
  Sort(1,m);
  new(t);
  t^.v:=p[1];
  t^.k:=random(1000);
  t^.p:=1;
  t^.s:=1;
  t^.l:=nil;
  t^.r:=nil;
  h:=1;
  tt:=1;
  for i:=1 to m do
  begin
    for j:=tt+1 to q[i,2] do
    begin
      new(v);
      v^.v:=p[j];
      v^.k:=random(1000);
      v^.p:=j;
      v^.s:=1;
      v^.l:=nil;
      v^.r:=nil;
      Ins(t);
      Turn(v);
    end;
    tt:=q[i,2];
    for j:=h to q[i,1]-1 do
      Del(j);
    h:=q[i,1];
    Print(t,q[i,3],i);
  end;
  for i:=1 to m do
    writeln(ans[i]);
End;

Begin
  Initialize;
  Main;
End.

• 变量名都是单字母…… (0) Jet605 2006-05-04 22:05:23