Lost Cows

Lost Cows

从后往前，如果第 K 头牛前面有 Ak 头比它低，那么它的身高 Hk 是数值 1~N 中第 Ak + 1 小的没有在{Hk+1 , Hk+2,......Hn}中出现的数，具体讲就是建立一个长度为 n 的 01 序列 b，起初全部为 1 。然后从 n  到 1  倒序扫描每个 Ai ，对每个 Ai 执行以下两个操作：

       1.查询序列 b 中第 Ai + 1 个 1 在什么位置，这个位置号就是第 i 头奶牛的身高 Hi。

       2.把 b[ H[ i ] ] 减一（从1变为0）

       直接用树状数组 + 二分即可完成

#include <bits/stdc++.h>

using namespace std;
const int maxn=10000;
int n,a[maxn],h[maxn],c[maxn];
int lowbit(int x) {
    return x & -x;
}

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

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

int search(int x) {
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (sum(mid) < x) l = mid + 1; else r = mid;
    }
    return l;
}
int main() {
    scanf("%d", &n);
    add(1, 1);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &a[i]);
        add(i, 1);
    }
    for (int i = n; i >= 1; i--) {
        h[i] = search(a[i] + 1);
        add(h[i], -1);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d
", h[i]);
    }
    return 0;
}