#P6424. 「JOI 2023 Final」石子排列 2

    ID: 5913 传统题 2000ms 1024MiB 尝试: 3 已通过: 2 难度: 4 上传者: 标签>难度分类普及+/提高-构造与建模不变量分析排序与序列处理离散化二分查找CF1600

「JOI 2023 Final」石子排列 2

「JOI 2023 Final」石子排列 2

题目描述

译自 JOI 2023 Final T1「碁石ならべ 2 / Stone Arranging 2」

JOI 君有 NN 个石子。石子从 11 到 NN 编号。每个石子的颜色用一个 11 到 10910^9 之间的整数表示(包括两端)。最初,第 i (1≤i≤N)i\ (1\le i\le N) 颗石子的颜色是 AiA_i。

现在开始,JOI 君会进行 NN 次操作。他会把这些石子在桌子上排成一排。第 i (1≤i≤N)i\ (1\le i\le N) 次操作按如下方式进行:

  1. JOI 君会把石子 ii 放在石子 i−1i-1 的右边,并与其相邻。然而,当 i=1i=1 时,JOI 君会把石子 11 放在桌子上。
  2. 如果在石子 1,2,…,i−11,2,\ldots,i-1 中,存在一个石子满足它当前的颜色和第 ii 个石子相同,令 jj 为这样的石子中下标最大的,然后 JOI 君会把石子 j+1,j+2,…,i−1j+1,j+2,\ldots,i-1 都涂成 AiA_i 颜色。

为了确认操作是否正确进行,JOI 君想提前知道在所有操作都进行之后,石子的颜色是什么。

给出这些石子的信息,写一个程序确定在 NN 次操作之后每个石子的颜色。

输入格式

第一行一个整数 NN,表示石子个数。

接下来 NN 行,每行一个整数 AiA_i,表示每个石子的颜色。

输出格式

输出 NN 个整数,第 i (1≤i≤N)i\ (1\le i\le N) 行表示 NN 次操作之后第 ii 个石子的颜色。

样例输入 1

6
1
2
1
2
3
2

样例输出 1

1
1
1
2
2
2

样例输入 2

10
1
1
2
2
1
2
2
1
1
2

样例输出 2

1
1
1
1
1
1
1
1
1
2

样例 1 说明

每次操作完成后,桌上的颜色依次为:

操作 颜色序列 说明
11 放下石子 11
22 1,21,2 放下石子 22
33 1,1,11,1,1 新放石子 33 后,把石子 22 涂成 11
44 1,1,1,21,1,1,2 此时没有颜色为 22 的旧石子,不重涂
55 1,1,1,2,31,1,1,2,3 放下石子 55
66 1,1,1,2,2,21,1,1,2,2,2 把石子 55 涂成 22

判断同色石子时要使用已经发生重涂后的当前颜色,不是各石子的初始 AjA_j。

数据范围与提示

对于全部数据,满足:

  • 1≤N≤2×1051\le N\le 2\times 10^5
  • 1≤Ai≤109 (1≤i≤N)1\le A_i\le 10^9\ (1\le i\le N)

详细附加限制及分值如下表所示。

子任务编号 附加限制 分值
11 N≤2 000N\le 2\ 000 2525
22 Ai≤2 (1≤i≤N)A_i\le 2\ (1\le i\le N) 3535
33 无附加限制 4040