分析

• 由题目可知，这n有牛的身高是1~n的一个排列。

• 我们可以从排在最后的一头牛开始考虑，假设$h_i$表示第i头牛前面有$h_i$头牛比它矮，则当考虑$h_n$时，表示第n头牛应该是第$h_n+1$矮的牛；因此当考虑第$h_i$头牛是，它应该是剩余高度中第$h_i+1$矮的牛（所谓剩余是指已经确定高度的数据不能参与进来）。

• 考虑上面的分析中存在什么操作：

（1）从剩余的数中，找出第K小的数；

（2）删除某个数；

• 这两个操作是平衡树的两个典型操作，但是平衡树很难写，我们考虑使用树状数组解决。

• 我们可以使用一个数组记录每个数据是否被使用过，记为数组a，$a[i]==1$表示高度i没有被使用过，$a[i]==0$表示已经存在某头牛的高度为i；设$sum(x)=\sum a[i], 1 \le i \le x$则上面的操作等价于：

（1）找到一个最小的x，使得sum(x)==K；

（2）将a[x]置为0，代表该高度已经被使用过。

• 第（2）个操作相当于单点加，第（1）个操作相当于区间和，可以使用树状数组解决。

• 对于第（1）个操作，因为sum(x)是x的一个单调递增函数，因此可以使用二分求解。

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int h[N];  // h[i]表示前面有h[i]头牛比当前牛矮
int ans[N];  // 最终这一列牛的高度
int tr[N];  // 维护上面分析中的数组a的前缀和, 我们并不需要将a定义出来

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

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {

    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &h[i]);

    // 初始化树状数组, 因为开始a中所有元素都为1
    // 所以根据tr[i]的定义，即tr[i] = a[i - lowbit(i) + 1, i]之和
    // tr[i] = lowbit(i)
    for (int i = 1; i <= n; i++) tr[i] = lowbit(i);

    for (int i = n; i; i--) {
        int k = h[i] + 1;  // 此时第i头牛的高度是所有牛当中第k小的
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = r;
        add(r, -1);  // 让a[i]变为0
    }

    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);

    return 0;
}