lb2003的个人博客

Lost Rivers
考虑倒序处理，最后一头牛的身高为$h[n]+1$，那么是不是意味着$h[n]+1$这个数(或高度、位置)已经有人了，无法对之后的牛产生贡献，那么是否有想到权值线段树，如果$i$被占用，就删去$i$这个位置的$1$。
可是按照蓝书上的思路，我选择打一种十分鬼畜的方法。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=1e5+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int c[N];int n;
void add(int x){for(;x<=n;x+=x&-x)--c[x];}
int p[21],a[N],h[N];
int main()
{
    p[0]=1;
    for(int i=1;i<20;i++)p[i]=p[i-1]<<1;
    qr(n);int t=log(n)/log(2);
    for(int i=1;i<=n;i++)
    {
        ++c[i];
        if(i+(i&-i)<=n)c[i+(i&-i)]+=c[i];
    }
    a[1]=1;
    for(int i=2;i<=n;i++)qr(a[i]),++a[i];
    for(int i=n;i;i--)
    {
        int ans=0,sum=0;
        for(int j=t;~j;j--)
            if((ans|p[j])<=n&&sum+c[ans|p[j]]<a[i])
            {
                sum+=c[ans|p[j]];
                ans|=p[j];
            }
        add(h[i]=ans+1);
    }
    for(int i=1;i<=n;i++)qw(h[i]),puts("");
    return 0;
}