分数: 1400 点
问题陈述
在这个问题中,“排列”总是意味着排列 (1,2,\cdots,N).
对于两种排列 p 和 q,让我们定义它们之间的距离, d(p,q),如下。
- 考虑制作 p 等于 q 通过重复交换两个相邻项 p。让 d(p,q) 是此处所需的最小交换次数。
此外,对于排列 x,让我们定义另一个排列 f(x) 如下。
- 让 y=(1,2,\cdots,N)。考虑排列 z 这样 d(x,z) \leq d(y,z)。让 f(x) 是这些排列中字典顺序最小的。
例如,当 x=(2,3,1),排列 z 这样 d(x,z) \leq d(y,z) 是 z=(2,1,3),(2,3,1),(3,1,2),(3,2,1)。 按字典顺序排列最小的是 (2,1,3),所以我们有 f(x)=(2,1,3).
给你一个排列 A=(A_1,A_2,\cdots,A_N)。 判断是否存在排列 x 这样 f(x)=A.
解决 输入文件中的 T 每个输入文件的测试用例。
序列的字典顺序是什么?
此处描述的算法确定不同序列之间的字典顺序 S 和 T.
下面,让 S_i 表示 i- 第一个元素 S。另外,让 S \lt T 和 S \gt T 意思是“S 按字典顺序小于 T“和”S 的字典顺序大于 T”,分别。
- 让 L 是以下较短者的长度 S 和 T。对于每个 i=1,2,\dots,L,让我们检查是否 S_i 和 T_i 相等。
- 如果有 i 这样 S_i \neq T_i,让 j 是最小的这样 i,并比较 S_j 和 T_j。如果 S_j 小于 T_j (作为数字),我们得出结论 S \lt T 并退出;如果 S_j 大于 T_j,我们得出结论 S \gt T 并退出。
- 如果没有 i 这样 S_i \neq T_i,比较长度 S 和 T。如果 S 短于 T,我们得出结论 S \lt T 并退出;如果 S 长于 T,我们得出结论 S \gt T 并退出。
约束
- 1 \leq T \leq 150000
- 2 \leq N \leq 300000
- (A_1,A_2,\cdots,A_N) 是一个排列 (1,2,\cdots,N).
- 总和 一个输入文件中的 N 不超过 300000.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例的格式如下:
N A_1 A_2 \cdots A_N
输出
对于每种情况,打印 Yes 如果有排列 x 这样 f(x)=A,和 No 否则。
样本输入 1
2 2 1 2 2 2 1
示例输出 1
Yes Yes
例如,当 A=(2,1),一个可以让 x=(2,1) 满足 f(x)=A.
示例输入 2
6 3 1 2 3 3 1 3 2 3 2 1 3 3 2 3 1 3 3 1 2 3 3 2 1
示例输出 2
Yes Yes Yes Yes No No
例如,当 A=(2,3,1),一个可以让 x=(3,2,1) 满足 f(x)=A.
示例输入 3
24 4 1 2 3 4 4 1 2 4 3 4 1 3 2 4 4 1 3 4 2 4 1 4 2 3 4 1 4 3 2 4 2 1 3 4 4 2 1 4 3 4 2 3 1 4 4 2 3 4 1 4 2 4 1 3 4 2 4 3 1 4 3 1 2 4 4 3 1 4 2 4 3 2 1 4 4 3 2 4 1 4 3 4 1 2 4 3 4 2 1 4 4 1 2 3 4 4 1 3 2 4 4 2 1 3 4 4 2 3 1 4 4 3 1 2 4 4 3 2 1
示例输出 3
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No No No No No No No No No No No No No