谜一样的牛

AcWing-244-谜一样的牛

分析

见《进阶指南》第209页。

实现

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

const int N = 100010;
int n, a[N], h[N], c[N], p[20];

int lowbit (int x) {
    return x & -x;
}
void add (int idx, int val) {
    while (idx <= n) {
        c[idx] += val;
        idx += lowbit(idx);
    }
}
int sum (int idx) {
    int res = 0;
    while (idx >= 1) {
        res += c[idx];
        idx -= lowbit(idx);
    }
    return res;
}

int main () {
    p[0] = 1;
    for (int i = 1; i <= 19; ++ i) p[i] = p[i - 1] * 2;

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

    for (int i = 1; i <= n; ++ i) add(i, 1);
    int t = log2(n);
    for (int i = n; i >= 1; -- i) {
        int ptr = 0, sum = 0;
        for (int j = t; j >= 0; -- j) {
            if (ptr + p[j] <= n && sum + c[ptr + p[j]] < a[i] + 1) {
                sum += c[ptr + p[j]];
                ptr += p[j];
            }
        }
        h[i] = ptr + 1;
        add(h[i], -1);
    }
    for (int i = 1; i <= n; ++ i) printf("%d\n", h[i]);
    return 0;
}