[AdditionalFile6169.zip](file://AdditionalFile6169.zip?type=additional_file)

#6169. 相似序列

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

给定长度为 $n$ 的整数序列 $A$，你需要回答 $q$ 个询问。询问给定两个子串 $[a, b]$ 和 $[c, d]$，要求你判断两个子串是否相似。

如果两个序列在各自排序后，除最多一个位置外，其他所有位置上的元素对应相等，那么我们认为两个序列相似。

请注意，给定的子串可以有公共部分，但不会互相影响。

输入格式

输入的第一行包含一个整数 $T$ ，代表测试数据的组数。接下来是 $T$ 组数据。
每组数据的第一行包含两个整数 $n$ 和 $q$，分别代表序列长度和询问数。
接下来一行包含 $n$ 个由空格分隔的整数 $A_1, A_2, \dots , A_n$。
接下来 Q 行，每行描述一个询问。询问以四个整数 $a, b, c, d$ 表示，其中 $a$ 和 $b$ 为第一个子串的左右端点，$c$ 和 $d$ 为第二个子串的左右端点。

输出格式

对于每个询问，判断两个子串是否相似，并相应输出一行 YES 或者 NO 。

样例

输入

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

输出

YES
NO
YES

在第一个询问中，第一个子串在排序后为 $[1, 3, 4]$，第二个子串在排序后为 $[2, 3, 4]$。除第 $1$ 个位置上的元素外，两个子串对应相等，故相似。 在第二个询问中，第一个子串在排序后为 $[1, 3]$，第二个子串在排序后为 $[3, 4]$。两个位置上的元素均不相等，故不相似。 在第三个询问中，第一个子串在排序后为 $[2, 3, 4]$，第二个子串在排序后为 $[2, 3, 4]$。两个子串对应位置完全相等，故相似。

数据范围与提示

• 所有数据满足：

  • $1 \leq a \leq b \leq n$
  • $1 \leq c \leq d \leq n$
  • $b − a = d − c$

• 子任务 1（10 分）

  • $1 \leq T \leq 3$
  • $1 \leq n,q \leq 10 ^ 3$
  • $1 \leq A[i] \leq 10 ^ 3$

• 子任务 2（20 分）

  • $1 \leq T \leq 3$
  • $1 \leq n \leq 10 ^ 5$
  • $1 \leq q \leq 10 ^ 4$
  • $1 \leq A_i \leq 10 ^ 5$

• 子任务 3（70 分）

  • $1 \leq T \leq 3$
  • $1 \leq n,q \leq 10 ^ 5$
  • $1 \leq A_i \leq 10 ^ 5$