| 比赛 | 
    树状数组练习 | 
    评测结果 | 
    AAAAAAA | 
    | 题目名称 | 
    Lost Cows | 
    最终得分 | 
    100 | 
    | 用户昵称 | 
    zjzhe | 
    运行时间 | 
    0.063 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    3.77 MiB  | 
    | 提交时间 | 
    2025-06-12 15:23:27 | 
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],rk[N];
struct Treap{int lc,rc,val,rnd,siz;}tr[N];
int tot,rt;
int New(int x){
	tr[++tot]={0,0,x,rand(),1};
	return tot;
}
void up(int x){
	tr[x].siz=tr[tr[x].lc].siz+tr[tr[x].rc].siz+1;
}
int merge(int L,int R){
	if(!L||!R)return L+R;
	if(tr[L].rnd<tr[R].rnd){
		tr[L].rc=merge(tr[L].rc,R);
		up(L);return L;
	}else{
		tr[R].lc=merge(L,tr[R].lc);
		up(R);return R;
	}
}
void split(int x,int k,int &L,int &R){
	if(!x)return L=R=0,void();
	if(tr[tr[x].lc].siz+1<=k)L=x,split(tr[x].rc,k-tr[tr[x].lc].siz-1,tr[x].rc,R);
	else R=x,split(tr[x].lc,k,L,tr[x].lc);
	up(x);
}
int kth(int x,int k){
    if(tr[tr[x].lc].siz+1==k)return x;
    if(tr[tr[x].lc].siz<k)return kth(tr[x].rc,k-tr[tr[x].lc].siz-1);
    if(tr[tr[x].lc].siz>=k)return kth(tr[x].lc,k);
} 
int main(){
	freopen("lostcows.in","r",stdin);
	freopen("lostcows.out","w",stdout);
	srand(time(0));cin>>n;
	for(int i=2;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)rt=merge(rt,New(i));
	for(int i=n,l,r,y;i>=1;i--)rk[i]=tr[kth(rt,a[i]+1)].val,split(rt,a[i],l,r),split(r,1,y,r),rt=merge(l,r);
	for(int i=1;i<=n;i++)cout<<rk[i]<<'\n';
	return 0;
}