座標圧縮で値を順位に変える

10^9のように大きい値でも、大小関係だけ必要なら登場する値の順位へ置き換えられます。

言語：Python / 計算量：O(N log N)

前提：set と辞書で「見たこと」を記録 / ソートで順序を作る

考え方

1. 重複を除きソートします。
2. 小さい順に0,1,2,…を割り当てます。
3. 元の値が必要なら対応配列を保持します。

具体例

[100,5,100,30]→[2,0,2,1]。等しい値は同じ順位になります。

実装

a=[100,5,100,30]
values=sorted(set(a))
rank={x:i for i,x in enumerate(values)}
print([rank[x] for x in a])

注意する条件

距離は保存されません。100-30=70でも圧縮後の差は1。面積を計算するときは元の座標差を使います。

確認問題

[100,5,30] で値30の0始まり順位は？

実装課題

N と整数列 A。座標圧縮した列を出す。N≤200000、|A_i|≤10^18。

入力:
4
100 5 100 30
出力:
2 0 2 1

n=int(input());a=list(map(int,input().split()));v=sorted(set(a));r={x:i for i,x in enumerate(v)}
print(*(r[x] for x in a))

読了の記録・下書き・メモへ