type node=record
       x,y,num,k:longint;
     end;
var ans,pretty,fa,count:array[0..100100] of longint;
    son:array[0..100100,1..2] of longint;
    a:array[0..50010] of node;
    j,root,n,q,i,t:longint;
procedure mid(x:longint);
  begin
    if son[x,1]<>0 then mid(son[x,1]);
    write(pretty[x],' ');
    if son[x,2]<>0 then mid(son[x,2]);
  end;

procedure update(x:longint);
  begin
    count[x]:=count[son[x,1]]+count[son[x,2]]+1;
  end;

procedure clear(x:longint);
  begin
    son[x,1]:=0;
    son[x,2]:=0;
    count[x]:=1;
  end;

procedure swap(var a,b:node);
  var c:node;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure rotate(x,w:longint);
  var y:longint;
  begin
    y:=fa[x];
    if fa[y]<>0 then
    begin
      if son[fa[y],1]=y then son[fa[y],1]:=x
      else son[fa[y],2]:=x;
    end;
    fa[x]:=fa[y];
    son[y,3-w]:=son[x,w];
    if son[x,w]<>0 then fa[son[x,w]]:=y;
    son[x,w]:=y;
    fa[y]:=x;
    update(y);
    update(x);
  end;

procedure splay(x:longint);
  var y:longint;
  begin
    while fa[x]<>0 do
    begin
      y:=fa[x];
      if fa[y]=0 then
      begin
        if son[y,1]=x then rotate(x,2)
        else rotate(x,1);
      end
      else begin
        if son[fa[y],1]=y then
        begin
          if son[y,1]=x then
          begin
            rotate(y,2);
            rotate(x,2);
          end
          else begin
            rotate(x,1);
            rotate(x,2);
          end;
        end
        else begin
          if son[y,1]=x then
          begin
            rotate(x,2);
            rotate(x,1);
          end
          else begin
            rotate(y,1);
            rotate(x,1);
          end;
        end;
      end;
    end;
    update(x);
    root:=x;
  end;

function succ(x:longint):longint;
  var p:longint;
  begin
    p:=son[x,2];
    while son[p,1]<>0 do p:=son[p,1];
    exit(p);
  end;

function kth(x:longint):longint;
  var p:longint;
  begin
    p:=root;
    while p<>0 do
    begin
      if count[son[p,1]]+1=x then exit(pretty[p]);
      if count[son[p,1]]+1>x then p:=son[p,1]
      else begin
        x:=x-count[son[p,1]]-1;
        p:=son[p,2];
      end;
    end;
  end;

procedure insert(x:longint);
  var p:longint;
  begin
    inc(t);
    clear(x);
    if t=1 then
    begin
      root:=x;
      fa[x]:=0;
    end
    else begin
      p:=root;
      repeat
        inc(count[p]);
        if pretty[p]>pretty[x] then
        begin
          if son[p,1]=0 then break;
          p:=son[p,1];
        end
        else begin
          if son[p,2]=0 then break;
          p:=son[p,2];
        end;
      until false;
      fa[x]:=p;
      if pretty[p]>pretty[x] then son[p,1]:=x else son[p,2]:=x;
      splay(x);
    end;
  end;

procedure delete(x:longint);
  var p,y:longint;
  begin
    splay(x);
    dec(t);
    if t=0 then
    begin
      root:=0;
      t:=0;
      fillchar(fa,sizeof(fa),0);
      fillchar(son,sizeof(son),0);
      fillchar(count,sizeof(count),0);
      exit;
    end;
    if (son[x,1]<>0) and (son[x,2]<>0) then
    begin
      p:=succ(x);
      y:=fa[p];
      if y<>x then
      begin
        son[y,1]:=son[p,2];
        if son[p,2]<>0 then fa[son[p,2]]:=y;
        update(y);
      end;
      root:=p;
      fa[p]:=0;
      son[p,1]:=son[x,1];
      fa[son[x,1]]:=p;
      if y<>x then
      begin
        son[p,2]:=son[x,2];
        fa[son[x,2]]:=p;
      end;
    end
    else begin
      if son[x,1]<>0 then
      begin
        root:=son[x,1];
        fa[son[x,1]]:=0;
      end
      else if son[x,2]<>0 then
      begin
        root:=son[x,2];
        fa[son[x,2]]:=0;
      end;
    end;
    update(root);
    clear(x);
  end;

procedure sort(l,r: longint);
  var i,j,x,y: longint;
  begin
    i:=l;
    j:=r;
    x:=a[(l+r) shr 1].x;
    repeat
      while (a[i].x<x) do inc(i);
      while (x<a[j].x) do dec(j);
      if not(i>j) then
      begin
        swap(a[i],a[j]);
        inc(i);
        j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

begin
  readln(n,q);
  for i:=1 to n do
    read(pretty[i]);
  readln;
  for i:=1 to q do
  begin
    readln(a[i].x,a[i].y,a[i].k);
    a[i].num:=i;
  end;
  count[0]:=0;
  sort(1,q);
{  for i:=1 to q do
    writeln(a[i].x,' ',a[i].y);}
  root:=0;
  for i:=a[1].x to a[1].y do
    insert(i);
  ans[a[1].num]:=kth(a[1].k);
{   mid(root);
    readln;
    writeln(t);}
  for i:=2 to q do
  begin
    if a[i].x>a[i-1].y then
    begin
      root:=0;
      t:=0;
      fillchar(fa,sizeof(fa),0);
      fillchar(son,sizeof(son),0);
      fillchar(count,sizeof(count),0);
      for j:=a[i].x to a[i].y do
      begin
        insert(j);
      end;
    end
    else begin
      for j:=a[i-1].y+1 to a[i].y do
        insert(j);
      for j:=a[i-1].x to a[i].x-1 do
      begin
        delete(j);
      end;
    end;
{     mid(root);
    readln;
    writeln(t);}
    ans[a[i].num]:=kth(a[i].k);
  end;
  for i:=1 to q do
    writeln(ans[i]);
end.

• Re:求数据，离线splay一直WA (5) phile_OI 2014-03-01 21:12:59