← 返回题目列表

Codeforces · 2138/B

B. Antiamuny想要学习互换

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

对于长度为$$$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$$$ 进行排序所需的最小操作数(同时使用操作 1 和操作 2),并将 $$$g(b)$$$ 定义为按非降序对数组 $$$b$$$ 进行排序所需的最少操作数 仅使用操作 1.

数组 $$$b$$$ 是 完美 如果$$$f(b) = g(b)$$$。换句话说,与仅使用相邻交换相比,使用操作 2 的能力并不会减少对数组 $$$b$$$ 进行排序所需的操作数。

您将获得一个长度为 $$$n$$$$$^{\text{∗}}$$$ 的排列 $$$a$$$,并且必须回答 $$$q$$$ 查询。每个查询由两个整数 $$$l$$$ 和 $$$r$$$ ($$$1\le l\le r\le n$$$) 组成,表示子数组 $$$a[l\ldots r]$$$$$$^{\text{†}}$$$。对于每个查询,确定子数组 $$$a[l\ldots r]$$$ 是否完美。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^{\text{†}}$$$子数组$$$a[l\ldots r]$$$包含从索引$$$l$$$到$$$r$$$的所有元素,即$$$[a_l, a_{l + 1}, a_{l + 2}, \ldots, a_r]$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$) - 数组 $$$a$$$ 的长度和查询的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots ,a_n$$$ ($$$1 \le a_i \le n$$$) - 排列 $$$a$$$ 中的元素。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) - 查询子数组的左端点和右端点。

保证所有测试用例的 $$$n$$$ 之和和 $$$q$$$ 之和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,输出“是" 如果查询的子数组 $$$a[l\ldots r]$$$ 是完美的,并且 "NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

2
5 5
1 5 4 3 2
1 2
1 5
3 5
1 4
2 5
5 5
3 2 1 4 5
1 1
4 5
1 4
2 5
3 4

输出
复制

YES
NO
NO
NO
NO
YES
YES
NO
YES
YES

注意

在第一个测试用例中:

  • 查询 1:$$$a[1\ldots 2] = [1, 5]$$$ 已按升序排序。因此, $$$f(a[1\ldots 2]) = g(a[1\ldots 2]) = 0$$$ 并且子数组 $$$a[1\ldots 2]$$$ 是完美的。
  • 查询 2:$$$a[1\ldots 5] = [1, 5, 4, 3, 2]$$$。 $$$f(a[1\ldots 5]) = 4$$$ 因为我们可以使用以下操作序列对数组进行排序:

    $$[1,\textbf{5},4,\textbf{3},2] \xrightarrow{\text{op} 2} [1,3,4,\textbf{5},\textbf{2}] \xrightarrow{\text{op} 1} [1,3,\textbf{4},\textbf{2},5]\xrightarrow{\text{op} 1} [1,\textbf{3},\textbf{2},4,5] \xrightarrow{\text{op} 1}[1,2,3,4,5]$$

    另一方面,$$$g(a[1\ldots 5]) = 6$$$,因为它需要至少 $$$6$$$ 相邻交换才能对 $$$a[1\ldots 5]$$$ 进行排序。由于 $$$f(a[1\ldots 5]) \neq g(a[1\ldots 5])$$$,子数组 $$$a[1\ldots 5]$$$ 并不完美。

  • 查询 3:$$$a[3\ldots 5] = [4, 3, 2]$$$。 $$$f(a[3\ldots 5]) = 1$$$ 因为我们可以使用以下操作序列对数组进行排序:

    $$[\textbf{4}, 3,\textbf{2}] \xrightarrow{\text{op} 2} [2, 3, 4]$$

    另一方面,$$$g(a[3\ldots 5]) = 3$$$,因为它需要至少 $$$3$$$ 相邻交换才能对 $$$a[3\ldots 5]$$$ 进行排序。由于 $$$f(a[3\ldots 5]) \neq g(a[3\ldots 5])$$$,子数组 $$$a[3\ldots 5]$$$ 并不完美。