一开始我没有什么思路（太蒻了qwq），想不到这道题和树状数组的联系是什么。我主要是觉得仅仅根据题目给出的信息，难以确定每头牛的实际高度是多少。

现在重新回顾这道题，我认为，凡是这类一开始时，所求答案完全未知的问题，应该在边界问题上寻找原问题的突破口。因为对于那些靠近问题空间“中部”的子问题，其“左右两边”可以认为和它是本质相同的子问题，没有办法直接解决。因此我们应该着重考虑边界处的子问题。

在本题中，我们首先考虑最后一头牛。由于它已经统计了在它之前的所有牛，因此，假如它比x头牛高，则它的高度一定是$x + 1$。我们采取从后往前考虑的方式，就是因为题目给出了“每头牛已知在自己前面比自己矮的牛的个数”这一条件，从后往前可以少考虑很多问题。

由于每头牛的高度各不相同且取遍区间$[1,n]$，因此，对于倒数第二头牛而言，它应该在除去上述$x + 1$的区间$[1,n]$中，选取$A_{n-1} + 1$小的数。其他的牛以此类推。

假如建立一个全部元素为1的数列，某个位置的数为1代表这个高度还不知道是哪头牛的，那么就用树状数组维护该数列的前缀和，若某个位置的前缀和等于$A_i + 1$，此时的下标就是要找的数。选择这个数后，将相应位置的1置0.可以二分这个位置。

二分版：

#include <cmath>
#include <cstdio>
using namespace std;

const int MAXN = 100005;

int n;
int seq[MAXN], height[MAXN], c[MAXN], prefix[MAXN];

inline int lowbit(int x)
{
    return x & -x;
}

inline int query(int x)
{
    int res = 0;
    while (x) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

inline void modify(int x, int val)
{
    while (x <= n) {
        c[x] += val;
        x += lowbit(x);
    }
}

void init()
{
    scanf("%d", &n);
    for (int i = 2;i <= n;++i) scanf("%d", &seq[i]);
    for (int i = 1;i <= n;++i) c[i] = lowbit(i);
}

void work()
{
    for (int i = n;i >= 1;--i) {
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (query(mid) < seq[i] + 1) l = mid + 1;
            else r = mid;
        }
        height[i] = l;
        modify(l, -1);
    }
    for (int i = 1;i <= n;++i) {
        printf("%d\n",height[i]);
    }
}

int main()
{
    init();
    work();
    return 0;
}

倍增版：

运用了“每个正整数都可以被分解为2的不重复次幂之和”这一结论，最终我们停下来的位置再加上一就是答案。

为什么要加上1呢？看一下这行代码：

if (pos + (1 << s) <= n && sum + c[pos + (1 << s)] < seq[i] + 1)
...

注意到后面用的是小于而非小于等于。如果使用小于等于的话，有可能前面的条件满足，而又因为pos后一大段全部是0（对前缀和没有贡献），导致后面的条件也满足。这时pos就会比答案大。而改成小于就不会这样了，仅仅是需要在最后加上一。

另外，sum + c[pos + (1 << s)]也不会导致重复累加。大家可以看看P203的图，不难发现，如果每次枚举2的次幂，而且是严格降序枚举的话，是不会有重复区间的。

#include <cmath>
#include <cstdio>
using namespace std;

const int MAXN = 100005;

int n;
int seq[MAXN], prefix[MAXN], height[MAXN], c[MAXN];

inline int lowbit(int x)
{
    return x & -x;
}

inline int query(int x)
{
    int res = 0;
    while (x) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

inline void modify(int x)
{
    while (x <= n) {
        c[x]--;
        x += lowbit(x);
    }
}

void init()
{
    scanf("%d", &n);
    for (int i = 2;i <= n;++i) scanf("%d", &seq[i]);
    for (int i = 1;i <= n;++i) c[i] = lowbit(i);
}

void work()
{
    int maxs = log2(n);
    for (int i = n;i >= 1;--i) {
        int pos = 0, sum = 0;
        for (int s = maxs;s >= 0;--s) {
            if (pos + (1 << s) <= n && sum + c[pos + (1 << s)] < seq[i] + 1) {
                sum += c[pos + (1 << s)];
                pos += (1 << s);
            }
        }
        modify(height[i] = pos + 1);
    }
    for (int i = 1;i <= n;++i) {
        printf("%d\n",height[i]);
    }
}

int main()
{
    init();
    work();
    return 0;
}