比赛 树状数组练习 评测结果 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;
}