← 返回题目列表

AtCoder · agc068_c

C. 球重新分配

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

分数: 1200 点

问题陈述

有 N 盒子编号为 1 to N,和 N 球编号为 1 to N.

您已为 Snuke 分配了以下内容 程序 作为作业。

  • 将每个球放入他喜欢的任何盒子中。同一个盒子里可以放多个球,也可以有没有球的盒子。
  • 对于 i = 1, 2, \cdots, N 按此顺序执行以下操作。
    • 如果框 i 不包含球,不执行任何操作。
    • 如果框 i 包含球,将它们全部取出并排成一行 以他喜欢的任何顺序。让 k 是取出的球数,并且 (x_1, x_2, \cdots, x_k) 是该行中的球号。对于每个 1 \leq j \leq k, 放球 x_j 放入盒子 x_{j+1}。在这里, x_{k+1} 意味着 x_1。所有这些将球放入盒子的操作都是同时发生的。

他声称他已经完成了作业并向你报告最终状态。 具体来说,他说那个球 i 装在盒子里 A_i 手术后。

您怀疑他是否正确执行了该程序。 确定他报告的状态是否是该程序的可能结果。

有 T 每个输入的测试用例。

约束

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq N
  • 总和 N 每个输入中的所有测试用例最多 250000.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

对于每个测试用例,打印 Yes 如果 Snuke 报告的状态是该过程的可能结果,并且 No 否则。


示例输入 1

5
3
1 1 1
3
2 2 2
5
1 2 3 4 5
10
8 3 8 10 1 5 3 1 6 4
10
1 5 1 2 4 8 8 6 7 3

示例输出 1

Yes
No
Yes
No
Yes

考虑第一个测试用例。 以下步骤产生 Snuke 报告的状态,所以答案是 Yes.

  • 放球 1, 2, 3 放入盒子中 1, 1, 2。
  • 从盒子里拿出球 1 并将它们排列为 (2, 1).
    • 放球 2 放入盒子 1.
    • 放球 1 放入盒子 2.
  • 从盒子里拿出球 2 并将它们排列为 (1, 3).
    • 放球 1 放入盒子 3.
    • 放球 3 放入盒子 1.
  • 从盒子里拿出球 3 并将它们排列为 (1).
    • 放球 1 放入盒子 1.
  • 现在,球 1, 2, 3 全部在盒子里 1.