CF2138B Antiamuny Wants to Learn Swap

对于长度为 $m$ 的数组 $b$，你可以进行以下两种操作： 1. 选择一个下标 $1\le i\le m-1$，然后交换 $b_i$ 和 $b_{i+1}$ 的值。 2. 选择一个下标 $1\le i\le m-2$，然后交换 $b_i$ 和 $b_{i+2}$ 的值。 但是，你至多只能执行一次操作 $2$。 我们定义 $f(b)$ 表示将数组 $b$ 通过这两种操作排序为非递减序列所需的最小操作次数，$g(b)$ 表示只使用操作 $1$（相邻交换）将数组 $b$ 排序为非递减序列所需的最小操作次数。 如果对每个 $b$ 都有 $f(b) = g(b)$，那么这个数组 $b$ 被称为“完美的”（即 perfect）。换句话说，能否使用操作 $2$ 并不会减少数组 $b$ 排序所需的最小操作次数。 现给定一个长度为 $n$ 的排列 $a$，你需要回答 $q$ 个询问。每个询问包含两个整数 $l$ 和 $r$（$1\le l\le r\le n$），表示子数组 $a[l\ldots r]$。对于每个查询，判断子数组 $a[l\ldots r]$ 是否为完美的。 *注$^{\ast}$：长度为 $n$ 的排列是指包含 $1$ 到 $n$ 的 $n$ 个互不相同的整数。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（数字 $2$ 重复），$[1,3,4]$ 也不是排列（$n=3$ 但包含 $4$）。* *注$^{\dagger}$：子数组 $a[l\ldots r]$ 包含从下标 $l$ 到 $r$ 的所有元素，即 $[a_l, a_{l+1}, a_{l+2}, \ldots, a_r]$。*

每个测试包含多组测试数据。第一行输入一个整数 $t$（$1\le t\le 5\times10^4$），表示测试组数。 每组测试数据第一行输入两个整数 $n$ 和 $q$（$1\le n, q\le 5\times 10^5$）——排列 $a$ 的长度和查询数量。 接下来一行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i \le n$）——排列 $a$ 的各个值。 接下来的 $q$ 行，每行输入两个整数 $l$ 和 $r$（$1\le l\le r\le n$），表示查询的子数组为 $a[l\ldots r]$。 保证所有测试数据中 $n$ 之和与 $q$ 之和不超过 $5\times 10^5$。

对于每个查询，如果子数组 $a[l\ldots r]$ 是完美的，输出 "YES"，否则输出 "NO"。 你可以使用任意大小写形式的 YES/NO。例如 "yEs", "yes", "Yes", "YES" 都视为是肯定回答。

在第一个测试用例中： - 查询 1：$a[1\ldots2]=[1,5]$ 已经是递增排序，所以 $f(a[1\ldots2])=g(a[1\ldots2])=0$，该子数组是完美的。 - 查询 2：$a[1\ldots5]=[1,5,4,3,2]$。$f(a[1\ldots5])=4$，可以如下操作： $$ [1,\textbf{5},4,\textbf{3},2] \xrightarrow{\text{操作2}} [1,3,4,\textbf{5},\textbf{2}] \xrightarrow{\text{操作1}} [1,3,\textbf{4},\textbf{2},5]\xrightarrow{\text{操作1}} [1,\textbf{3},\textbf{2},4,5] \xrightarrow{\text{操作1}} [1,2,3,4,5] $$ 而 $g(a[1\ldots5])=6$，至少需要 $6$ 次相邻交换。由于 $f(a[1\ldots 5])\neq g(a[1\ldots 5])$，所以该子数组不是完美的。 - 查询 3：$a[3\ldots5]=[4,3,2]$。$f(a[3\ldots5])=1$，可以如下操作： $$ [\textbf{4},3,\textbf{2}] \xrightarrow{\text{操作2}} [2,3,4] $$ 而 $g(a[3\ldots5])=3$，至少需要 $3$ 次相邻交换。由于 $f(a[3\ldots5])\neq g(a[3\ldots5])$，所以该子数组不是完美的。 由 ChatGPT 5 翻译