P9349 [JOI 2023 Final] 石子排列 2 / Stone Arranging 2
题目描述
JOI 君有 $N$ 颗围棋子。这些棋子从 $1$ 到 $N$ 编号。每颗棋子的颜色是一个介于 $1$ 和 $10^9$ 之间的整数（包含 $1$ 和 $10^9$）。一开始，第 $i$ 颗棋子（$1 \le i \le N$）的颜色是 $A_i$。
接下来，JOI 君将进行 $N$ 次操作。他会将棋子排成一行放在桌子上。第 $i$ 次操作（$1 \le i \le N$）将按如下方式进行：
1. JOI 君将第 $i$ 颗棋子放在第 $i-1$ 颗棋子的右边。但是，当 $i = 1$ 时，JOI 君会将第 1 颗棋子放在桌子上。
2. 如果在第 $1, 2, \cdots, i-1$ 颗棋子中有一颗棋子的当前颜色与第 $i$ 颗棋子的颜色相同，设 $j$ 为此类棋子的最大索引，JOI 君将用颜色 $A_i$ 涂色第 $j+1, j+2, \cdots, i-1$ 颗棋子。
为了确认操作是否正确执行，JOI 君想提前知道所有操作执行后棋子的颜色。
给定围棋子的相关信息，编写一个程序来确定 $N$ 次操作后棋子的颜色。
输入格式
从标准输入读取以下数据。
> $N$
> $A_1$
> $A_2$
> $\vdots$
> $A_N$
输出格式
向标准输出写入 $N$ 行。第 $i$ 行（$1 \le i \le N$）应包含第 $i$ 颗棋子在 $N$ 次操作后颜色。
说明/提示
## 样例
### 样例 1
操作按下表执行。
最终，第 1, 2, 3, 4, 5, 6 颗棋子的颜色分别为 1, 1, 1, 2, 2, 2。
此样例输入满足子任务 1, 3 的约束。
### 样例 2
此样例输入满足所有子任务的约束。
## 约束
- $1 \le N \le 2 \times 10^5$。
- $1 \le A_i \le 10^9$ ($1 \le i \le N$)。
- 给定的值都是整数。
## 子任务
1. (25 分) $N \le 2 000$。
2. (35 分) $A_i \le 2$ ($1 \le i \le N$)。
3. (40 分) 无额外约束。
题面翻译由 ChatGPT-4o 提供。