额
> 归并树，总WA
> 请问哪位有pascal的标程？C的看着太别扭，有的还不明白……
> program pku_2104;
> type
>   treetype=record
>     lf,rf,left,right:longint;
>   end;
>   treetype2=record
>     left,right,zhi,size:longint;
>   end;
> var
>   tree:array[0..200005]of treetype;{外边的树}
>   treen:array[0..3400000]of treetype2;{建在外树顶点上的树}
>   root:array[1..100000]of longint;{内部树的根顶点编号}
>   a,b:array[0..100000]of longint;
>   bianh,yings,yong:array[0..100000]of longint;{bianh第i名是第几个数，yings第i个数是第几名}
>   i,j,k,n,m,p,q,r,s,len,lenn,sj,xj:longint;
> procedure swap(var a,b:longint);
> var
> t:longint;
> begin
> t:=a;
> a:=b;
> b:=t;
> end;
> procedure kuaipai(l,r:longint);
>   var i,j,min,x:longint;
>   begin
>     i:=l;j:=r;min:=a[(l+r) div 2];
>     repeat
>       while a[i]<min do inc(i);
>       while a[j]>min do dec(j);
>       if i<=j then begin
>                     swap(a[i],a[j]);
>                     swap(bianh[i],bianh[j]);
>                     inc(i);dec(j);
>                   end;
>     until i>j;
>     if i<r then kuaipai(i,r);
>     if j>l then kuaipai(l,j);
> end;
> procedure kuaipai2(l,r:longint);
>   var i,j,min,x:longint;
>   begin
>     i:=l;j:=r;min:=yong[(l+r) div 2];
>     repeat
>       while yong[i]<min do inc(i);
>       while yong[j]>min do dec(j);
>       if i<=j then begin
>                     swap(yong[i],yong[j]);
>                     inc(i);dec(j);
>                   end;
>     until i>j;
>     if i<r then kuaipai2(i,r);
>     if j>l then kuaipai2(l,j);
> end;
> procedure build2(b,e:longint);
> var
>   t,k:longint;
> begin
>   t:=(b+e)div 2;
>   inc(lenn);
>   treen[lenn].size:=e-b+1;
>   treen[lenn].zhi:=yong[t];
>   k:=lenn;
>   if b<e then begin
>     treen[k].left:=lenn+1;
>     build2(b,t);
>     treen[k].right:=lenn+1;
>     build2(t+1,e);
>   end;
> end;
> procedure build1(b,e:longint);
> var
>   t,k:longint;
> begin
>   t:=(b+e) div 2;
>   inc(len);
>   tree[len].lf:=b;
>   tree[len].rf:=e;
>   root[len]:=lenn+1;
>   for i:=b to e do yong[i]:=yings[i];
>   kuaipai2(b,e);
>   build2(b,e);
>   k:=len;
>   if b<e then begin
>     tree[k].left:=len+1;
>     build1(b,t);
>     tree[k].right:=len+1;
>     build1(t+1,e);
>   end;
> end;
> function find2(j,p:longint):longint;
> var
> than,tmp,t:longint;
> begin
> tmp:=p;
> than:=0;
> while treen[tmp].size<>1 do
> begin
> if j>treen[tmp].zhi then begin
> than:=than+treen[treen[tmp].left].size;
> tmp:=treen[tmp].right;
> end
> else tmp:=treen[tmp].left;
> end;
> if j>treen[tmp].zhi then inc(than);
> find2:=than;
> end;
> function find(b,e,j,p:longint):longint;
> var
> t,s:longint;
> begin
>   if (tree[p].lf>=b)and(tree[p].rf<=e) then begin
>     find:=find2(j,root[p]);
>     exit;
>   end;
>   s:=0;
>   t:=(tree[p].lf+tree[p].rf)div 2;
>   if b<=t then s:=s+find(b,e,j,tree[p].left);
>   if e>t then s:=s+find(b,e,j,tree[p].right);
>   find:=s;
> end;
> begin
>   assign(input,'pku_2104.in');
>   assign(output,'pku_2104.out');
>   reset(input);
>   rewrite(output);
>   readln(n,m);
>   len:=0;
>   lenn:=0;
>   fillchar(treen,sizeof(treen),0);
>   fillchar(tree,sizeof(tree),0);
>   fillchar(root,sizeof(root),0);
> fillchar(bianh,sizeof(bianh),0);
>   fillchar(yong,sizeof(yong),0);
>   fillchar(yings,sizeof(yings),0);
>   
>   for i:=1 to n do read(a[i]);
>   b:=a;
>   for i:=1 to n do bianh[i]:=i;
>   kuaipai(1,n);
>   for i:=1 to n do yings[bianh[i]]:=i;
>   build1(1,n);
>   for i:=1 to m do begin
>   readln(p,q,r);
>   xj:=1;
>   sj:=n;
>   r:=r-1;
>   while xj<sj-1 do
>   begin
>     j:=(sj+xj)div 2;
>     s:=find(p,q,j,1);
>     {if s=r then break
>     else }if s>r then sj:=j-1 else xj:=j;
>   end;
>   s:=find(p,q,xj+1,1);
>   if (s=r)and(xj=sj-1) then writeln(b[bianh[xj+1]]) else writeln(b[bianh[xj]]);
>   end;
>   close(input);
>   close(output);
> end.

• Re:求救！总是RE (21) xycking 2010-02-18 22:00:56