因为二分套树状数组是两个log,然后树状数组+倍增的一个log做法不是特别理解.
所以,我用权值线段树来解此题(有关权值线段树,可见这篇blog的第一部分)
主要思路:权值线段树上二分
倒序扫描输入的数组$a$,对于奶牛$i$查询未被确定的高度中第$a_i+1$小的即为其高度
先将所有1~n的高度的出现次数都设为1(即加上1)
查询k-th时,
- 对于叶子节点,直接返回代表的点
- 对于其它节点,如果左孩子的总出现次数不小于k,返回去左孩子查询kth的值;否则返回去右孩子查询k-左孩子的总出现次数th的值.
查询完后记得将查询的结果(当前奶牛的高度)出现次数设为0(即减去1)
由上,我们得到一个权值线段树上二分的一个log做法,总时间复杂度$O(nlogn)$
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;
typedef std::pair<ll,ll> pll;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
ll abs(ll x)
{
return x>0?x:-x;
}
/**********/
#define MAXN 100011
ll n;
struct Segment_Tree//权值线段树
{
ll t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
typedef unsigned un;
void pushup(un num)
{
rt=tl+tr;
}
void modify(un x,ll k,un l=1,un r=n,un num=1)
{
if(l==r)
{
if(l==x)rt+=k;
return;
}
un mid=(l+r)>>1;
if(x<=mid)modify(x,k,l,mid,num<<1);
if(x>mid)modify(x,k,mid+1,r,num<<1|1);
pushup(num);
}
ll Qkth(ll k,un l=1,un r=n,un num=1)
{
if(l==r)return l;
un mid=(l+r)>>1;
if(k<=tl)return Qkth(k,l,mid,num<<1);
else return Qkth(k-tl,mid+1,r,num<<1|1);
}
}sgt;
ll a[MAXN],h[MAXN];
int main()
{
n=read();
for(ll i=1;i<=n;++i)sgt.modify(i,1);
for(ll i=2;i<=n;++i)a[i]=read();
for(ll i=n;i;--i)
{
ll ans=sgt.Qkth(a[i]+1);
sgt.modify(ans,-1);
h[i]=ans;
}
for(ll i=1;i<=n;++i)printf("%lld\n",h[i]);
return 0;
}
不愧是学军中学的学生