選手 \(i\) がリタイアするときは、選手 \(1\) から選手 \((i-1)\) のうちスタミナ地が \(L_i\) 未満の人の人数だけ列の左側から抜けています。この人数を \(k_i\) とすると、選手 \(i\) がリタイアするときは左から \(i-k_i\) 番目にいます。

この \(k_i\) を各 \(i\) について求めたいです。これは以下のようにして求められます。

• 長さ \(N\) の配列 \(C=(0,0,\ldots,0)\) を用意する。
• \(i=1,2,\ldots,n\) について以下を行う
  • \(k_i \larr \sum_{j=1}^{L_i-1}C_j\)
  • \(C_{L_i} \larr 1\)

このアルゴリズムを愚直に実行すると時間計算量 \(\mathrm{O}(N^2)\) となりますが、 \(C\) に対する一点変更区間和を求める操作なので Binary Indexed Tree(Fenwick Tree)を用いて高速に求めることができます。Binary Indexed Treeでは配列に対する一点変更と区間和がクエリあたり時間計算量 \(\mathrm{O}(\log N)\) で求めることができます。

よって、時間計算量 \(\mathrm{O}(N \log N)\) でこの問題が解くことができます。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    for (auto& e : l) cin >> e;
    atcoder::fenwick_tree<int> fw(n + 1);
    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        int rank = i + 1 - fw.sum(0, l[i]);
        res[l[i] - 1] = rank;
        fw.add(l[i], 1);
    }
    for (auto e : res) cout << e << endl;
}