#6169. 相似序列

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: bluto

题目描述

给定长度为 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