题目详情题解（0）讨论（0）提交记录（0）

AT_agc058_e.[AGC058E] Nearer Permutation

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在本题中，提到“顺序排列”时，指的是 $ (1,2,\cdots,N) $ 的一个排列。

对于两个排列 $ p,q $，定义它们的距离 $ d(p,q) $ 如下：

  • 通过不断交换 $ p $ 中相邻的两个元素，将 $ p $ 变为 $ q $。所需的最小操作次数即为 $ 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) $ 时，满足 $ 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 $ 个元素为 $ S_i $。若 $ S $ 的字典序小于 $ T $，记为 $ S<T $，大于则记为 $ S>T $。

  1. 取 $ S $ 和 $ T $ 中较短的长度为 $ L $。依次比较 $ i=1,2,\dots,L $ 时 $ S_i $ 和 $ T_i $ 是否相等。
  2. 若存在 $ S_i\neq T_i $ 的 $ i $，取最小的此类 $ i $ 为 $ j $。若 $ S_j $ 小于 $ T_j $，则 $ S<T $，否则 $ S>T $，算法结束。
  3. 若所有 $ S_i=T_i $，则比较 $ S $ 和 $ T $ 的长度，短者字典序小。若 $ S $ 比 $ T $ 短，则 $ S<T $，否则 $ S>T $，算法结束。

输入格式

输入以如下格式从标准输入读入。

$ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $

每个测试用例如下格式：

$ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

输出格式

对于每个测试用例，若存在排列 $ x $ 使得 $ f(x)=A $，输出 Yes，否则输出 No。

输入输出样例

  • 输入#1

    2
2
1 2
2
2 1

    输出#1

    Yes
Yes

  • 输入#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

  • 输入#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

说明/提示

限制条件

  • $ 1\leq T\leq 150000 $
  • $ 2\leq N\leq 300000 $
  • $ (A_1,A_2,\cdots,A_N) $ 是 $ (1,2,\cdots,N) $ 的一个排列
  • 每个输入文件中 $ N $ 的总和不超过 $ 300000 $
  • 所有输入值均为整数

样例解释 1

例如 $ A=(2,1) $ 时，取 $ x=(2,1) $，则 $ f(x)=A $。

样例解释 2

例如 $ A=(2,3,1) $ 时，取 $ x=(3,2,1) $，则 $ f(x)=A $。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页