0x42 树状数组 例题3：谜一样的牛

· · 个人记录 

【题意】
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。
现在这n头奶牛站成一列，已知第i头牛前面有Ai头牛比它低，求每头奶牛的身高。

【输入格式】
第1行：输入整数n。
第2..n行：每行输入一个整数Ai,第i行表示第i头牛前面有Ai头牛比它低。
（注意：因为第1头牛前面没有牛，所以并没有将它列出）

【输出格式】
输出包含n行，每行输出一个整数表示牛的身高。
第i行输出第i头牛的身高。

【数据范围】
1≤n≤10^5 
【输入样例】
5
1
2
1
0
【输出样例】
2
4
5
3
1

设 ans[k] 表示第 k 头牛的身高，
显而易见地，ans[n]=a[n]+1 

if(d[n-1]<d[n]) ans[n-1]=a[n-1]+1
else ans[n-1]=a[n-1]+2

以此类推，我们发现,如果说第k头牛的前面有 d[k] 头牛比它矮, 那么它的身高 ans[k] 就是数值 1~n 中第 d[k+1] 小的没有在 ans[k+1],...,ans[n] 中出现过的数

在此先献上优美的暴力代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
inline int read()
{
    int x=0;bool f=false;
    char ch=getchar();
    while(ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
int d[N],ans[N];
bool b[N];
int main()
{
    int n=read();
    for(int i=2;i<=n;i++) d[i]=read();
    for(int i=n;i>=1;i--)
    {
        int len=0;
        for(int j=1;j<=n;j++) if(!b[j])
        {
            len++;
            if(len==d[i]+1) {b[j]=true;ans[i]=j;break;}
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

由于ACwing的数据太水，亲测N≤8000，↑可以过
但是这很明显不科学，蒟蒻强迫自己树状数组优化，
问题转化为：有长度为 N 的01串（第k位表示“排名k”是否出现过，出现过为0），求第 d[k+1] 个 1 的位置 

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
inline int read()
{
    int x=0;bool f=false;
    char ch=getchar();
    while(ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
int sum[N];
inline int lowbit(int x) {return x&-x;}
inline void change(int x,int k)
{
    while(x<=N)
    {
        sum[x]+=k;
        x+=lowbit(x);
    }
}
inline int getsum(int x)
{
    int ret=0;
    while(x>=1)
    {
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
int d[N],ans[N];
int main()
{
    int n=read();
    change(1,1);
    for(int i=2;i<=n;i++) d[i]=read(),change(i,1);
    for(int i=n;i>=1;i--)
    {
        int l=1,r=n,p;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(getsum(mid)>=d[i]+1) r=mid-1,p=mid;
            else l=mid+1;
        }
        ans[i]=p;
        change(p,-1);
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}