概要

各山 \(i\) について、標高 \(A_i\) より 厳密に高い 標高を持つ山が全体に何個あるかを求めます。

考察

素朴にやるなら、各 \(i\) について全ての山 \(j\) を見て \(A_j > A_i\) を数えますが、これは \(O(N^2)\) となり、\(N \le 2 \times 10^5\) では間に合いません。

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

• 求めたいのは「自分より高い山の個数」＝「全体 \(N\) 個のうち、自分以下（\(A_j \le A_i\)）の個数を引いたもの」
• つまり \(B_i = N - \#\{j \mid A_j \le A_i\}\) と書けます。

では \(\#\{j \mid A_j \le A_i\}\) を高速に求めるにはどうするか？ 標高配列をソートしておけば、「\(A_i\) 以下の要素がソート済み配列のどこまであるか」を二分探索で求められます。

例：\(A = [4, 2, 4, 1]\) のとき、ソートすると \(SA = [1,2,4,4]\)
- \(A_i=2\) のとき、\(2\) 以下は \([1,2]\) の 2 個 → 高い山は \(4-2=2\) 個
- \(A_i=4\) のとき、\(4\) 以下は 4 個 → 高い山は \(4-4=0\) 個

「厳密に高い」なので、同じ標高は数えない点に注意が必要です。このため「\(A_i\) 以下の個数」を数えるのがちょうど良く、Python では bisect_right が使えます（同値を右側まで含めた位置を返す）。

アルゴリズム

1. 配列 \(A\) をソートして \(SA\) を作る。
2. 各 \(a = A_i\) について、bisect_right(SA, a) を使って
   • \(a\) 以下の要素数 \(k\) を得る（\(k = \#\{j \mid A_j \le a\}\)）
3. 答えは \(B_i = N - k\)。

bisect_right を使う理由： - bisect_right(SA, a) は「\(a\) を挿入しても順序が保たれる最も右の位置」＝「\(a\) 以下の要素数」を返す
- よって \(N - bisect_right(SA, a)\) が「\(a\) より大きい要素数」になります。

計算量

• 時間計算量: ソートに \(O(N \log N)\)、各要素の二分探索に \(O(\log N)\) を \(N\) 回で \(O(N \log N)\)、合計 \(O(N \log N)\)
• 空間計算量: ソート配列 \(SA\) などで \(O(N)\)

実装のポイント

• 「厳密に高い」なので、同じ標高は除外する必要があります。そのため bisect_left ではなく bisect_right を使い、「\(A_i\) 以下」を数えるのが簡潔です。

• 出力は \(N\) 個を空白区切りで 1 行にするため、文字列にして " ".join(...) でまとめると高速です。

  ソースコード

import sys
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    SA = sorted(A)
    ans = [str(N - bisect_right(SA, a)) for a in A]
    print(" ".join(ans))

if __name__ == "__main__":
    main()

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