#ABC036C. 【模板】离散化

【模板】离散化

AtCoder-abc036_c

题目描述

\hspace{15pt}有 nn 个人排成一列,第 ii 个人的座压为 aia_i。すぬけ君希望在保持大小关系不变的前提下,把这些座压数据压缩后保存。

\hspace{15pt}请构造一个数列 {b1,b2,…,bn}\{b_1, b_2, \dots, b_n\},满足以下条件:

1. {\hspace{20pt}}_\texttt{1.}\,每个 bib_i 都是非负整数;

2. {\hspace{20pt}}_\texttt{2.}\,若 ai<aja_i < a_j,则 bi<bjb_i < b_j;

3. {\hspace{20pt}}_\texttt{3.}\,若 ai=aja_i = a_j,则 bi=bjb_i = b_j;

4. {\hspace{20pt}}_\texttt{4.}\,在所有满足上述条件的数列中,b1,b2,…,bnb_1, b_2, \dots, b_n 中的最大值最小。

\hspace{15pt}可以证明,满足这些条件的数列 bb 是唯一的。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表人数。

\hspace{15pt}此后 nn 行,第 ii 行输入一个整数 ai(0≦ai≦109)a_i \left(0 \leqq a_i \leqq 10^9\right) 代表第 ii 个人的座压。

输出格式

\hspace{15pt}输出 nn 行,第 ii 行输出一个整数 bib_i。

测试样例

5
3
3
1
6
1
1
1
0
2
0

样例 1 解释

\hspace{15pt}座压依次为 3,3,1,6,13, 3, 1, 6, 1,其中出现过的不同取值从小到大依次为 1,3,61, 3, 6。

∙ \hspace{23pt}\bullet\,把 11 压缩为 00;

∙ \hspace{23pt}\bullet\,把 33 压缩为 11;

∙ \hspace{23pt}\bullet\,把 66 压缩为 22。

\hspace{15pt}于是得到 b1=1b_1=1,b2=1b_2=1,b3=0b_3=0,b4=2b_4=2,b5=0b_5=0。这样既保持了原有的大小关系与相等关系,最大值 22 也已经是所有合法方案中最小的。

6
8
3
8
1
5
3
3
1
3
0
2
1

提示

\hspace{15pt}对于 3030 分的测试点,满足 1≦n≦1031 \leqq n \leqq 10^3。

\hspace{15pt}对于另外 3030 分的测试点,满足 0≦ai≦1050 \leqq a_i \leqq 10^5。