【题意】
已知每头牛左边比他名次小的牛的数量,求所有牛的名次
【输入】
第一行n
接下来n-1行描述2~n头牛左边名次比其小的牛的数量
【输出】
n行,表示各个牛的名次
线段树
每个点表示只考虑剩余牛,左边牛比当前牛名次小的数量
每次找最靠右的值为0的牛,就是当前名次的牛
然后把其右边的节点值全部减一
重复以上步骤n次就得出解
program poj2182; var tot,n,i,j,k:longint; ans:array [0..8001] of longint; decr,min,left,right:array [0..200001] of longint; procedure update (now:longint);inline; begin if left[now]=0 then begin inc(tot); left[now]:=tot; end; if right[now]=0 then begin inc(tot); right[now]:=tot; end; if decr[now]<>0 then begin min[left[now]]:=min[left[now]]+decr[now]; decr[left[now]]:=decr[left[now]]+decr[now]; min[right[now]]:=min[right[now]]+decr[now]; decr[right[now]]:=decr[right[now]]+decr[now]; decr[now]:=0; end; end; function find :longint; var l,r,mid,now:longint; begin l:=1; r:=n; now:=0; while l<>r do begin update(now); mid:=(l+r) div 2; if min[right[now]]=0 then begin l:=mid+1; now:=right[now]; end else begin r:=mid; now:=left[now]; end; end; exit(l); end; procedure insert (p,s,e,l,r,now:longint); var mid:longint; begin if (s=l)and(e=r) then begin min[now]:=min[now]+p; decr[now]:=decr[now]+p; exit; end; update(now); mid:=(l+r) div 2; if e<=mid then insert(p,s,e,l,mid,left[now]) else if s>mid then insert(p,s,e,mid+1,r,right[now]) else begin insert(p,s,mid,l,mid,left[now]); insert(p,mid+1,e,mid+1,r,right[now]); end; if min[left[now]]<min[right[now]] then min[now]:=min[left[now]] else min[now]:=min[right[now]]; end; begin read(n); tot:=0; for i:=2 to n do begin read(k); insert(k,i,i,1,n,0); end; for i:=1 to n do begin k:=find; ans[k]:=i; if k<n then insert(-1,k+1,n,1,n,0); insert(100000,k,k,1,n,0); end; for i:=1 to n do writeln(ans[i]); end.