题目描述

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

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

输入格式
第1行：输入整数n。

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

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

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

数据范围
$1 \le n \le 10^5 $

样例

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

算法1

二分 + 树状数组 $O(nlog^2n)$

从后向前开始遍历, 第n头牛的身高必为$A_n + 1$, 到了$A_{n-1}$头时, 就要判断
若$A_{n-1}$ $<$ $A_n$, 则$H_{n -1} = A_{n-1} + 1 $
若$A_{n-1}$ $\ge$ $A_n$, 则$H_{n -1} = A_{n-1} + 2 $

依此类推, 对于$A_k$只需找第$A_k+1$小的且没有在${H_{k + 1},H_{k +2},…,H_n}$中没有出现过的数
而这道题的巧妙之处就在于构造一个初始全为1的b序列
用树状数组$C[]$来维护其前缀和, 那么查询第$A_i+1$个$1$在前缀和数组$C[]$中的位置, 就是第i头奶牛的身高
虽有将$C[i]$减1
用二分来确定位置

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 100010;
int a[N], b[N], c[N], h[N];
int n;

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

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

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

bool check(int t, int mid)
{
    int x = query(mid);
    if(x >= t) return true;
    else return false;
}

int main()
{
    cin >> n;
    for(int i = 2; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) add(i, 1);

    LL res = n * (n + 1) / 2;
    for(int i = n; i >= 2; --i)
    {
        // 查询第Ai + 1 个1在什么位置, 这个位置就是Hi
        int t = a[i] + 1;
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(t, mid)) r = mid;
            else l = mid + 1;
        }
        add(l, -1);
        res -= l;
        h[i] = l;
    }
    h[1] = res;
    for(int i = 1; i <= n; ++i) cout << h[i] << endl;

    return 0;
}