概要

スタミナ値の小さい順に選手が列から抜けていくとき、各選手が抜ける直前に「左から何番目にいるか」を高速に求める問題です。

考察

選手は最初は位置 \(1,2,\dots,N\) に並んでいますが、途中で誰かが抜けると左に詰められるため、単純に「元の位置」を出力するだけでは不正解になります。

重要な観察は次の通りです。

• ある選手（元の位置 \(i\)）がリタイアする直前の順位（左から何番目か）は、その時点で残っている選手のうち、元の位置が \(i\) 以下の人数に等しい。
  • なぜなら、詰められても「相対的な順序」は保たれるため、左にいるのは「元の位置が小さいまま残っている人」だけだからです。

素朴にシミュレーションすると、 - リタイアするたびに配列から削除して詰め直す（リストの削除）→ 1回あたり \(O(N)\) になり、合計 \(O(N^2)\) で \(N \le 2\times 10^5\) では TLE になります。

そこで、 - 「まだ残っているか」を \(1/0\) で管理し、 - ある位置 \(i\) までに残っている人数（前方累積和）を高速に求められればよい、 という形に問題を言い換えます。

アルゴリズム

次の手順で解きます。

1. スタミナ値 \(k\) の選手が元の列のどこにいるかを配列 pos に記録する

   • pos[k] = その選手の初期位置 i
   • 入力は順列なので必ず一意に決まります。

2. 長さ \(N\) の配列 \(A\) を考え、最初は全員残っているので

   • \(A[i]=1\)（位置 \(i\) の選手が残っている）
     これを Fenwick Tree（BIT） で管理します。

3. スタミナ値 \(k=1..N\) の順に処理する：

   • その選手の初期位置を \(i = \text{pos}[k]\) とする
   • BIT で \(\sum_{j=1}^{i} A[j]\) を計算する
     これが「リタイア直前の左からの順位」
   • その選手がリタイアするので \(A[i] \leftarrow 0\)、つまり BIT に add(i, -1) をする

具体例

例えば \(N=5\)、初期位置がそのままで、リタイア順（スタミナ値順）が位置 \(3 \to 1 \to 5 \to 2 \to 4\) だとします。

• 最初 \(A=[1,1,1,1,1]\)
• 位置3が抜ける直前：\(\sum_{1..3}=3\) → 出力 3、抜けた後 \(A=[1,1,0,1,1]\)
• 次に位置1：\(\sum_{1..1}=1\) → 出力 1、抜けた後 \(A=[0,1,0,1,1]\)
• …というように「前方の残存人数」を出すだけで、詰め直しを直接行わずに済みます。

計算量

• 時間計算量: \(O(N \log N)\)
  （各 \(k\) について BIT の sum と add を1回ずつ）
• 空間計算量: \(O(N)\)
  （pos と BIT 配列）

実装のポイント

• BIT は 1-indexed で実装するのが定石なので、位置も \(1..N\) で統一します。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み取ると高速です。

• 出力も join でまとめて行うと速くなります。

  ソースコード

import sys

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    L = data[1:]
    pos = [0] * (n + 1)
    for i, v in enumerate(L, start=1):
        pos[v] = i

    bit = BIT(n)
    for i in range(1, n + 1):
        bit.add(i, 1)

    out = []
    for k in range(1, n + 1):
        i = pos[k]
        out.append(str(bit.sum(i)))
        bit.add(i, -1)

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。