非常感谢ls神牛的程序，我就是照着你的改的，把指针改成了数组模拟的了。呵呵

program PKU_2761_Feed_the_dogs;

  const
    maxN=1000000;	//这里我开的10n过的，应该是多少我不清楚，望神牛解答
    maxM=50000;
    
  type
    TQuery=record
      l,r,k,id:longint
    end;
    
  var
    n,m,root,numNode:longint;
    a,left,right,fa,key,size:array[0..maxN] of longint;
    q:array[1..maxM] of TQuery;
    ans:array[1..maxM] of longint;
    
    function leftRotate(i:longint):longint;
      var
        j:longint;
      begin
        j:=right[i];
        right[i]:=left[j];
        left[j]:=i;
        fa[j]:=fa[i];
        fa[i]:=j;
        if right[i]<>0 then fa[right[i]]:=i;
        size[j]:=size[i];
        size[i]:=size[left[i]]+size[right[i]]+1;
        exit(j);
      end;
      
    function rightRotate(i:longint):longint;
      var
        j:longint;
      begin
        j:=left[i];
        left[i]:=right[j];
        right[j]:=i;
        fa[j]:=fa[i];
        fa[i]:=j;
        if left[i]<>0 then fa[left[i]]:=i;
        size[j]:=size[i];
        size[i]:=size[left[i]]+size[right[i]]+1;
        exit(j);
      end;
      
    function newNode(f,k:longint):longint;
      begin
        inc(numNode);
        key[numNode]:=k;
        fa[numNode]:=f;
        size[numNode]:=1;
        exit(numNode);
      end;
      
    procedure splay(i:longint);
      var
        f,g:longint;
        pg:^longint;
      begin
        while fa[i]<>0 do begin
          f:=fa[i];
          g:=fa[f];
          if g=0 then begin
            if i=left[f] then root:=rightRotate(f)
            else root:=leftRotate(f);
            break;
          end;
          if fa[g]=0 then pg:=@root
          else if g=left[fa[g]] then pg:=@left[fa[g]]
          else pg:=@right[fa[g]];
          if f=left[g] then begin
            if i=left[f]  then begin 
              pg^:=rightRotate(g);
              pg^:=rightRotate(f);
            end else begin
              left[g]:=leftRotate(f);
              pg^:=rightRotate(g);
            end;
          end else begin
            if i=right[f] then begin
              pg^:=leftRotate(g);
              pg^:=leftRotate(f);
            end else begin
              right[g]:=rightRotate(f);
              pg^:=leftRotate(g);
            end;
          end;
        end;
      end;
    
    procedure insert(k:longint);
      var
        i,j:longint;
      begin
        if root=0 then begin
          root:=newNode(0,k);
          exit;
        end;
        i:=root;
        inc(size[root]);
        if k<key[i] then j:=left[i] else j:=right[i];
        while j<>0 do begin
          inc(size[j]);
          i:=j;
          if k<key[j] then j:=left[j] else j:=right[j];
        end;
        if k<key[i] then begin
          left[i]:=newNode(i,k);
          splay(left[i]);
        end else begin
          right[i]:=newNode(i,k);
          splay(right[i]);
        end;
      end;
        
    function union(a,b:longint):longint;
      var
        i,j:longint;
      begin
        i:=a;
        while right[i]<>0 do i:=right[i];
        splay(i);
        j:=b;
        while left[j]<>0 do j:=left[j];
        splay(j);
        fa[i]:=j;
        inc(size[j],size[i]);
        left[j]:=i;
        exit(j);
      end;
        
    procedure delete(k:longint);
      var
        i,l,r:longint;
      begin
        i:=root;
        while key[i]<>k do
          if k<key[i] then i:=left[i] else i:=right[i];
        splay(i);
        if (left[i]=0) and (right[i]=0) then root:=0
        else if left[i]=0 then begin root:=right[i]; fa[right[i]]:=0;  end
        else if right[i]=0 then begin root:=left[i]; fa[left[i]]:=0; end
        else begin
          l:=left[i]; r:=right[i];
          fa[l]:=0; fa[r]:=0; root:=0;
          root:=union(l,r);
        end;
        key[i]:=-1;
      end;
        
    function select(k:longint):longint;
      var
        i:longint;
      begin
        i:=root;
        while k<>size[left[i]]+1 do
          if k<size[left[i]]+1 then i:=left[i] else begin
            dec(k,size[left[i]]+1);
            i:=right[i];
          end;
        exit(key[i]);
      end;
          
    function lessThan(var a,b:TQuery):boolean;
      begin
        if a.l<b.l then exit(true)
        else if a.l>b.l then exit(false)
        else if a.r>b.r then exit(true)
        else exit(false);
      end;
          
    procedure qSort(l,r:longint);
      var
        i,j:longint;
        x,tmp:TQuery;
      begin
        i:=l; j:=r; x:=q[(i+j)>>1];
        repeat
          while lessThan(q[i],x) do inc(i);
          while lessThan(x,q[j]) do dec(j);
          if i<=j then begin
            tmp:=q[i]; q[i]:=q[j]; q[j]:=tmp;
            inc(i); dec(j);
          end;
        until i>j;
        if i<r then qSort(i,r);
        if j>l then qSort(l,j);
      end;
      
    procedure init;
      var
        i:longint;
      begin
        readln(n,m);
        for i:=1 to n do read(a[i]);
        readln;
        for i:=1 to m do 
          with q[i] do begin
            readln(l,r,k);
            id:=i;
          end;
        qSort(1,m);
      end;
      
    function max(a,b:longint):longint;
      begin if a>b then exit(a) else exit(b); end;
        
    function min(a,b:longint):longint;
      begin if a<b then exit(a) else exit(b); end;
        
    procedure main;
      var
        i,j:longint;
      begin
        for j:=q[1].l to q[1].r do
          insert(a[j]);
        ans[q[1].id]:=select(q[1].k);
        for i:=2 to m do begin
          if q[i].l>q[i-1].r then begin
            for j:=q[i-1].l to q[i-1].r do delete(a[j]);
            for j:=q[i].l to q[i].r do insert(a[j]);
          end else if (q[i].l<=q[i-1].r) and (q[i].r>q[i-1].r) then begin
            for j:=q[i-1].r+1 to q[i].r do insert(a[j]);
            for j:=q[i-1].l to q[i].l-1 do delete(a[j]);
          end else begin
            for j:=q[i-1].l to q[i].l-1 do delete(a[j]);
            for j:=q[i].r+1 to q[i-1].r do delete(a[j]);
          end;
          ans[q[i].id]:=select(q[i].k);
        end;
      end;
            
    procedure print;
      var
        i:longint;
      begin
          for i:=1 to m do writeln(ans[i]);
      end;

begin
  init;
  main;
  print;
end.

• Re:我也发一个Splay伸展树版本的，3204ms过的，貌似常数还算小，静态数组做的 (14) Master_Chivu 2010-08-23 17:53:29
• 那个“pg:=@right[fa[g]]”中@是神马运算符？ (30) MyIdea 2011-08-01 10:48:18
  • Re:那个“pg:=@right[fa[g]]”中@是神马运算符？ (93) Hoblovski 2014-05-13 19:34:03
• 那个“pg:=@right[fa[g]]”中@是神马运算符？ (2) MyIdea 2011-08-01 10:48:26
• Re:我也发一个Splay伸展树版本的，3204ms过的，貌似常数还算小，静态数组做的 (6903) dyh495768138 2014-01-26 15:44:53