← 返回题目列表

AtCoder · agc058_e

E. 更接近的排列

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

分数: 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”,分别。

  1. 让 L 是以下较短者的长度 S 和 T。对于每个 i=1,2,\dots,L,让我们检查是否 S_i 和 T_i 相等。
  2. 如果有 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 并退出。
  3. 如果没有 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