分数: 900 点
问题陈述
给你一个序列 A = (A_1, A_2, \ldots, A_N) 长度 N。 每个元素可以是介于 1 和 N (含)或 -1.
Snuke 决定使用此序列创建一个新序列 A.
首先,全部替换 此序列中的 -1s A 之间的整数 1 和 N (含)。
接下来,创建一个序列 B = (B_1, B_2, \ldots, B_N) 长度 N 根据以下公式:
- B_i=A_{A_i}
找到字典顺序上最小的可能序列 B.
你被给予 T 测试用例。解决它们中的每一个。 一个输入文件中最多包含
序列的字典顺序是什么?
一个序列 C = (C_1,C_2,\ldots,C_N) is 按字典顺序较小 比序列 D = (D_1,D_2,\ldots,D_N) 当且仅当存在一个整数 1 \leq i \leq N 使得以下两者成立:
- (C_1,C_2,\ldots,C_{i-1}) = (D_1,D_2,\ldots,D_{i-1})
- C_i (在数值上)小于 D_i.
约束
- 1 \le T \le 10^5
- 1 \le N \le 5 \times 10^5
- 1 \le A_i \le N or A_i = -1.
- 总和 N 所有测试用例最多 5\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
N A_1 A_2 \dots A_N
输出
对于每个测试用例,输出按字典顺序排列的最小可能序列 B,以换行符分隔。
示例输入 1
3 4 4 -1 -1 3 5 5 4 5 3 1 7 -1 6 5 -1 7 -1 6
示例输出 1
3 1 4 1 1 3 1 5 5 1 1 7 1 6 1 1
在第一个测试用例中,序列 A 在 Snuke 被替换之前 (4,-1,-1,3).
假设他替换它得到 A=(4, 3, 1, 3).
然后, B=(A_4, A_3, A_1, A_3)=(3, 1, 4, 1).
不可能获得字典顺序更小的序列 B 比这个。