概要

各山について、自分より標高が厳密に高い山がいくつあるかを求める問題。

考察

各山 \(i\) に対して、\(A_i\) よりも大きい値が全体の中でいくつあるかを求めればよいです。
素朴な方法として、各山について他のすべての山と比較する \(O(N^2)\) の方法がありますが、
制約 \(N \leq 2 \times 10^5\) のもとでは時間内に計算できません（TLE）。

そこで、以下のような発想を使います：
- 各要素 \(A_i\) に対して、それより大きい要素の個数を高速に求めたい。
- これは、全体をソートしておけば、二分探索によって求めることができます。

具体的には： - 全体をソートした配列 sorted_A を用意する。 - 各 \(A_i\) に対して、sorted_A 中で \(A_i\) より大きい要素のうち最も左の位置を二分探索で求める。 - その位置以降の要素数が、\(A_i\) よりも大きい要素の個数となる。

たとえば、\(A = [3, 1, 4, 1, 5]\) の場合： - ソートすると sorted_A = [1, 1, 3, 4, 5] - 例えば \(A_1 = 3\) なら、bisect_right(sorted_A, 3) はインデックス 3 を返す。 - よって、3より大きい要素の個数は \(5 - 3 = 2\) 個。

このようにして、各クエリを \(O(\log N)\) で処理できます。

アルゴリズム

1. 入力された山の標高リスト \(A\) を読み込む。
2. \(A\) をソートしたリスト sorted_A を作る。
3. 各 \(A_i\) に対して、sorted_A 上で \(A_i\) より大きい要素の個数を求める。
   • これは、bisect.bisect_right(sorted_A, A_i) を使って、\(A_i\) より大きい最小のインデックスを取得。
   • 全体の要素数 \(N\) からそのインデックスを引いたものが答え。
4. 結果を順に出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)、各要素に対する二分探索に \(O(N \log N)\)
• 空間計算量: \(O(N)\)
  • ソートされた配列や結果を保存するため

実装のポイント

• bisect.bisect_right は「指定した値を超える最初の位置」を返すので、これを使うことで「より大きい要素の数」が簡単に求められる。
• 結果は最後にまとめて出力する方が効率的。

## ソースコード

```python
import bisect

N = int(input())
A = list(map(int, input().split()))

sorted_A = sorted(A)

result = []
for a in A:
    idx = bisect.bisect_right(sorted_A, a)
    result.append(N - idx)

print(' '.join(map(str, result)))

この解説は qwen3-coder-480b によって生成されました。