「POJ2182」Lost Cows

如果最后一头奶牛前面有 $A_n$ 头牛比它高，那么显然他的身高 $H_n=A_n+1$，

如果倒数第二头前面有 $A_{n-1}$ 头牛比它高，那么：

1.如果 $A_{n-1}<A_n$，那么它的身高为 $H_{n-1}=A_{n-1}+1$；

2.如果 $A_{n-1}\geqslant A_n$，那么它的身高为 $H_{n-1}=A_{n-1}+2$.

依此类推，如果第 $k$ 头牛前面有 $A_k$ 头比它高，那么它的身高 $H_k$ 是数值 $1\thicksim n$ 中第 $A_k+1$ 小的没有在 ${H_{k+1},H_{k+2},…H_n}$ 中出现过的数。

具体来说，我们建立一个长度为 $n$ 的 $01$ 序列 $b$，起初全部为 $1$，然后从 $n$ 到 $1$ 倒序扫描每个 $A_i$，对每个 $A_i$ 执行两个操作。

1.查询序列 $b$ 中第 $A_{i+1}$ 个 $1$ 在什么位置，这个位置号就是第 $i$ 头奶牛的身高 $H_i$。

2.把 $b[H_i]$ 从 $1$ 变为 $0$.

然后我们如果想查询身高，就直接对 $b$ 数组进行下标查询操作即可。

#include<stdio.h>
int n,a[8010],tree[8010];
int vis[8010],ans[8010];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=val;
}
int ask(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
        ans+=tree[i];
    return ans;
}
int two_devide(int x)
{
    int l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(ask(mid)<x)
            l=mid+1;
        else
            r=mid-1;
    }
    return l;
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        update(i,1);
    for(int i=n;i>=2;i--)
    {
        ans[i]=two_devide(a[i]+1);
        vis[ans[i]]=1;
        update(ans[i],-1);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            printf("%d\n",i);
            break;
        }
    for(int i=2;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}