学步园

这个题和2828是一样的，如果不不懂的地方看http://blog.csdn.net/Euler_M/archive/2011/03/30/6287853.aspx

这个题只是没告诉你第一头牛应该插在那，很简单嘛，第一头牛前面肯定没有牛，所以p[1]=0

其它都和2828一样，思想都是反过来想，把pos变成前面有多少个空位

/*<br /> * File: main.cpp<br /> * Author: Mi<br /> *<br /> * Created on 2011年3月30日, 上午10:17<br /> */<br /> #include <cstdlib><br /> #include <stdio.h><br /> #include <algorithm><br /> #define N 8005<br /> using namespace std;<br /> /*<br /> *<br /> */<br /> struct tree<br /> {<br /> int l,r,len;<br /> int mid()<br /> {<br /> return (l+r)>>1;<br /> }<br /> }T[N*4];<br /> int p[N],ans[N];<br /> void build(int l,int r,int root)<br /> {<br /> T[root].l=l,T[root].r=r;<br /> T[root].len=r-l+1;<br /> if(l==r)<br /> return ;<br /> int mid=T[root].mid();<br /> build(l,mid,root<<1);<br /> build(mid+1,r,root<<1|1);<br /> }<br /> int query(int pos,int root)<br /> {<br /> T[root].len--;<br /> if(T[root].l==T[root].r)<br /> return T[root].l;<br /> if(T[root<<1].len>=pos)<br /> return query(pos,root<<1);<br /> else<br /> {<br /> pos-=T[root<<1].len;<br /> return query(pos,root<<1|1);<br /> }<br /> }<br /> int main(int argc, char** argv)<br /> {<br /> int n;<br /> scanf("%d",&n);<br /> build(1,n,1);<br /> p[1]=0;<br /> for(int i=2;i<=n;i++)<br /> scanf("%d",&p[i]);<br /> for(int i=n;i>=1;i--)<br /> {<br /> int temp=query(p[i]+1,1);<br /> ans[i]=temp;<br /> }<br /> for(int i=1;i<=n;i++)<br /> printf("%d/n",ans[i]);<br /> return 0;<br /> }<br />