题目链接
题目大意
\(N（2 <= N <= 8,000）\)头奶牛有\(1..N\)范围内的独特品牌.对于每头排队的牛,知道排在那头牛之前的并比那头牛的品牌小的奶牛数目.根据这些数据,输出的确切排序。
题解
令输入数组为b[i];
可以发现最后一个奶牛可以确定为b[n]+1,由最后一个又可以推出倒数第二个，由此递推就好了,每次的答案就是序列中的第b[i]+1小的数,询问完后就将这个数从序列中删除。
至于怎么选那个数，就看你用什么数据结构维护了，我用的平衡树。
code
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9')
x=x*10+c-'0',c=getchar();
return x*f;
}
int cnt,root;
struct node{
int fa,ch[2],v,size,son;
}a[500001];
void pushup(int k){
a[k].son=a[a[k].ch[0]].son+a[a[k].ch[1]].son+a[k].size;
}
void turn(int x){
int y=a[x].fa,z=a[y].fa;
int k=x==a[y].ch[1],k2=y==a[z].ch[1];
a[z].ch[k2]=x,a[x].fa=z;
a[y].ch[k]=a[x].ch[k^1],a[a[x].ch[k^1]].fa=y;
a[x].ch[k^1]=y,a[y].fa=x;
pushup(y),pushup(x);
}
void splay(int x,int u){
while(a[x].fa!=u){
int y=a[x].fa,z=a[y].fa;
if(z!=u)
(a[y].ch[0]==x)^(a[z].ch[0]==y)?turn(x):turn(y);
turn(x);
}
if(u==0)
root=x;
}
void add(int x){
int u=root,f=0;
while(u&&a[u].v!=x)
f=u,u=a[u].ch[x>a[u].v];
if(u)
a[u].size++;
else{
++cnt;
u=cnt;
if(f)
(x>a[f].v)?a[f].ch[1]=u:a[f].ch[0]=u;
a[cnt].fa=f;
a[cnt].son=1;
a[cnt].size=1;
a[cnt].v=x;
}
splay(u,0);
}
void find(int x){
int u=root;
if(!u)
return ;
while(x!=a[u].v&&a[u].ch[x>a[u].v])
u=a[u].ch[x>a[u].v];
splay(u,0);
}
int hou(int x){
find(x);
int u=root;
if(a[u].v>x)
return u;
u=a[u].ch[1];
while(a[u].ch[0])
u=a[u].ch[0];
return u;
}
int qian(int x){
find(x);
int u=root;
if(a[u].v<x)
return u;
u=a[u].ch[0];
while(a[u].ch[1])
u=a[u].ch[1];
return u;
}
void delet(int x){
int l=qian(x),r=hou(x);
splay(l,0),splay(r,l);
int u=a[r].ch[0];
if(a[u].size>1)
a[u].size--,splay(u,0);
else
a[r].ch[0]=0;
}
int k_th(int x){
int u=root;
if(a[u].son<x)
return 0;
while(1){
int s=a[u].ch[0];
if(x>a[s].son+a[u].size)
x-=a[s].son+a[u].size,u=a[u].ch[1];
else
if(a[s].son>=x)
u=s;
else
return a[u].v;
}
}
int hh[100001],b[10001];
int main(){
add(-21474847);
add(21474837);
int n=read(),x;
for(int i=1;i<=n;i++)
add(i);
for(int i=2;i<=n;i++)
b[i]=read();
for(int i=n;i>=1;i--)
x=k_th(b[i]+2),hh[i]=x,delet(x);
for(int i=1;i<=n;i++)
printf("%d\n",hh[i]);
return 0;
}