座標圧縮

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /coordinate-compression#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /coordinate-compression#noredirect を利用してください。
name
座標圧縮
short description
座標圧縮とは、与えられた長さ $N$ の整数列 $a$ から、長さ $N$ の自然数列 $b$ であって要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるような $b$ を作ること。ただし「要素の順序関係が同じ」とは、任意の $i, j$ に対し $a_i \le a_j \leftrightarrow b_i \le b_j$ を満たすことを言う。このような $b$ は常に一意に存在し、単純な方法により $O(N \log N)$ で構成できる。
input
長さ $N$ の整数列 $a$
output
長さ $N$ の自然数列 $b$ であって、要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるもの
time complexity
$O(N \log N)$