题目描述

有 $n$ 头奶牛，已知它们的身高为 $1∼n$ 且各不相同，但不知道每头奶牛的具体身高。

现在这 $n$ 头奶牛站成一列，已知第 $i$ 头牛前面有 $A_i$ 头牛比它低，求每头奶牛的身高。

输入格式

第 $1$ 行：输入整数 $n$。

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

输出格式

输出包含 $n$ 行，每行输出一个整数表示牛的身高。

第 $i$ 行输出第 $i$ 头牛的身高。

数据范围

$1≤n≤10^5$

样例

输入样例：
5
1
2
1
0
输出样例：
2
4
5
3
1

算法1

(树状数组) $O(n \log ^ 2 n)$

模拟下样例

最后一头牛最矮
身高为1

第4头牛前面有一头比他矮
身高为3

第三头前面有两头比他矮
身高5

第二头前面有一头比他矮
身高为4

第一头身高为2

本题需要支持修改和查找第$k$小的数据结构
具体流程:
倒序遍历
前面有$A_i$头牛比第$i$头牛高，所以第$i$头牛的身高就是剩下身高的第$A_i+1$小数
然后删除第$i$头牛的身高即可

可以使用树状数组维护
加上二分

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, tr[N];
int a[N], res[N];

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 query(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", &a[i]);
    for (int i = 1; i <= n; i ++ ) tr[i] = lowbit(i);

    for (int i = n; i >= 1; i -- )
    {
        int l = 1, r = n, k = a[i] + 1;
        while (l < r)
        {
            int mid = l + r >> 1;

            if (query(mid) >= k) r = mid;
            else l = mid + 1;
        }

        res[i] = l;
        add(l, -1);
    }

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

    return 0;
}