244. 谜一样的牛

非常好的一道题，使用树状数组+二分将复杂度降至 $\ O(n \log(n) ^ 2)$ 。

题目大意：

给定每头牛前面的牛身高低于它的牛有多少，保证每头牛的身高为 $1 \sim n$ 的一个排列，求出每头牛的身高。

题目分析：

先看样例是如何操作的：

1. 对于第5头奶牛，此时可供选择的身高有 1 2 3 4 5，因为前面没有比他矮的奶牛，它又是最后一头，故身高只能是 $1$。

2. 对于第4头奶牛，此时可供选择的身高有 2 3 4 5，由前面有一头身高比他矮的牛，故他只能取到身高序列中的次小值，为$3$。

3. 对于第三头奶牛，此时可供选择身高有 2 4 5，前面有两头比他矮的牛，它的身高只能为第三小值 $5$。

依次类推，于是我们可以发现从后往前枚举，第 $i$ 头奶牛的身高为可选身高序列中第 $a_i +1$ 大值。

将问题转化为两个操作：

1. 删除一个身高。
2. 求出第 $k$ 小身高。

假定维护一个数组 $a$ ，一开始 $a$ 中所有元素为 $1$ ，表示身高 $i$ 还没有被选；如果被选了，则 $a_i=0$ 。那么删除操作就好做了。

接下来考虑求第 $k$ 小数，由于 $a$ 中元素只有 $0,1$ 两种可能，那么 $a$ 的前缀和肯定是 不降 的，满足二分条件，直接二分即可。

求第 $k$ 小数 $\Leftrightarrow$ 找出前缀和（$1 \sim n$ ）大于等于 $k$ 的第一个位置。

此时复杂度 $\ O(n^2)$ 不足以通过此题。

又观察到关于数组 $a$ 操作的性质：只用支持求前缀和+单点修改即可。

考虑使用树状数组。可将复杂度降至 $\ O(n \log(n) ^ 2)$ 。

AC_code

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn=1e5+5;
int n;
int tr[maxn],a[maxn],num[maxn],ans[maxn];
inline int lowbit(int x)
{
    return x&-x;
}
void add(int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k; 
}
int query(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i)) sum+=tr[i];
    return sum;
}

int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>n;
    for(int i=2;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,1),ans[i]=0;
    for(int i=n;i>=1;i--)
    {
        //找到剩余数中第k大
        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(query(mid)>=a[i]+1)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
//          cout<<l<<" "<<r<<endl;
        }
        ans[i]=l;
        add(l,-1);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}