題目連結

題目

題目描述

\(N (2 \leq N \leq 8,000)\) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

輸入描述

• Line 1: A single integer, N
• Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

輸出描述

• Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

範例1

輸入

5
1
2
1
0

輸出

2
4
5
3
1

題解

知識點：樹狀陣列，倍增，列舉。

首先需要一個事實，對於一個排列，要確定其中某個位置的數具體是多少，可以通過整個排列比它小的數位有多少個（或者比它大的數位有多少個）確定。現在這道題確定了各個位置的數的左邊比它小的數的個數，我們只需要知道在它右邊有多少個數比它小就行，因此我們從右往左列舉，依次確定數位。

首先用樹狀陣列維護右側出現的數位，隨後需要二分一個 \(x\) 通過比較 \(x - cnt_{<x} -1 < a_i\) 得知 \(x\) 是否小了還是大了，從而找到第一個 \(x - cnt_{<x} -1 = a_i\) 的點。注意，條件不能為 \(x - cnt_{<x} -1 \leq a_i\) ， 因為可能會出現連續一段剛好等於 \(a_i\) 的點，而我們只需要第一個的下標即可，如果用這個條件，我們得到的是最後一個下標。

當然，這個二分條件其實還可以更簡單，我們反過來記錄右側沒出現的數位，那麼 \(cnt_{<x}\) 直接代表左側比 \(x\) 小的數位個數，那麼條件為 \(cnt_{<x} < a_i\) 即可。

另外，二分套樹狀陣列查詢的複雜度是對數平方的，並不是最優的。我們可以直接使用樹狀陣列本身的倍增性質進行二分，是最優的對數複雜度。我封裝了兩個常用的函數，大於等於 lower_bound 和大於 upper_bound 。

這道題查詢 \(cnt_{<x} = a_i\) 的第一個點，我們 lower_bound 查詢即可。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class T>
class Fenwick {
    int n;
    vector<T> node;

public:
    Fenwick(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        node.assign(n + 1, T());
    }

    void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }

    T query(int x) {
        T ans = T();
        for (int i = x;i >= 1;i -= i & -i) ans += node[i];
        return ans;
    }
    T query(int l, int r) { return query(r) - query(l - 1); }

    int lower_bound(T val) {
        int pos = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (pos + i <= n && node[pos + i] < val) {
                pos += i;
                val -= node[pos];
            }
        }
        return pos + 1;
    }
    int upper_bound(T val) {
        int pos = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (pos + i <= n && node[pos + i] <= val) {
                pos += i;
                val -= node[pos];
            }
        }
        return pos + 1;
    }
};

int a[8007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 2;i <= n;i++) cin >> a[i];
    Fenwick<int> fw(n);
    for (int i = 1;i <= n;i++) fw.update(i, 1);

    vector<int> ans(n + 1);
    for (int i = n;i >= 1;i--) {
        ans[i] = fw.lower_bound(a[i] + 1);
        fw.update(ans[i], -1);
    }
    for (int i = 1;i <= n;i++) cout << ans[i] << '\n';
    return 0;
}