> 非常感谢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.