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