← 返回题目列表

AtCoder · arc209_d

D. A下标A_i

中文机器翻译题面 查看原题

分数: 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 比这个。