一、题意理解

我们有一个序列 $A$，每次询问给出两个长度相等的区间 $[a,b]$ 和 $[c,d]$。

定义“相似”：两个区间各自排序后，最多只有 一个位置 上的数不同，其他位置都相同。

换句话说，排序后的两个序列的 对称差（不同元素的集合）大小不超过 2，并且如果大小是 2，那么这两个不同的数在每个序列中恰好出现一次。

---

二、关键观察

设区间 $X = A[a..b]$，区间 $Y = A[c..d]$。

排序后比较，允许至多一对元素不同。

这意味着：

1. 两个区间的 多重集 要么完全相同，要么相差两个元素：
   $X$ 比 $Y$ 多一个 $x$，少一个 $y$，并且 $x \neq y$。
2. 不允许出现两个以上不同的元素，也不允许某个元素出现次数差大于 1。

---

三、问题转化

判断两个长度相等的区间是否相似，等价于：

• 计算两个区间中每个数值的出现次数（频率向量）。
• 找出所有数值 $v$ 满足 $cnt_X[v] \neq cnt_Y[v]$。
• 这些 $v$ 的个数必须 $\le 2$。
• 如果个数为 2，设为 $p$ 和 $q$，则必须满足： $ cnt_X[p] - cnt_Y[p] = 1,\quad cnt_X[q] - cnt_Y[q] = -1 $ 或者反过来。
• 如果个数为 0，则完全相同，显然相似。
• 如果个数为 1，则不可能（因为两个区间总长度相等，一个数频次变化必须有另一个数反向变化）。

---

所以条件简化为：
不同的数值恰好为 0 个或 2 个，并且频次差为 $+1$ 和 $-1$。

---

四、算法设计

直接对每个询问提取区间、排序、比较，复杂度 $O(\text{len} \log \text{len})$，对于大 $n,q$ 不可行。

我们需要快速比较两个区间的“多重集”是否最多差一对元素。

---

1. 哈希方法

我们可以对区间中数值的出现次数进行哈希，比较两个哈希值是否相等（完全相同）或者相差一对元素的贡献。

具体做法：

• 给每个数值 $v$ 分配一个随机权值 $h(v)$。
• 定义区间 $[l,r]$ 的哈希值为： $ H(l,r) = \sum_{v \in \text{区间}} cnt_{[l,r]}(v) \cdot h(v) $ 这可以通过前缀和 $pre[i][v]$ 计算，但数值范围大时不行。

更好的方法：用多项式哈希，$H = \sum_{x \in \text{多重集}} h(x)$ 不行，因为相同元素出现多次会重复加。

我们可以用 $H = \sum_{v} f(cnt_{[l,r]}(v)) \cdot h(v)$，其中 $f$ 是一个函数，但这样还是需要枚举所有出现过的 $v$。

---

2. 更实用的方法：频率向量的差

我们只需要知道两个区间频率向量的差向量（difference vector）是否满足条件。

差向量 $D[v] = cnt_X[v] - cnt_Y[v]$。

条件：

• $\sum_v |D[v]| = 2$（因为 $|D[p]| + |D[q]| = 2$，且 $D[p] = 1, D[q] = -1$ 或反过来）
• $\sum_v D[v] = 0$（总长度相等）

---

我们可以用 莫队算法 处理所有询问，维护每个值的出现次数，然后维护差向量中非零项的数量和具体值。

但 $n,q$ 大时莫队可能不够快。

---

3. 随机权值 + 哈希求和

一个巧妙的方法：

给每个值 $v$ 分配一个随机 64 位整数 $r(v)$。

定义区间哈希为： $H_1 = \sum_{v} cnt[v] \cdot r(v)$ 这可以快速用前缀和计算：$H_1(l,r) = \sum_{i=l}^r r(A[i])$。

再定义另一个哈希： $H_2 = \sum_{v} cnt[v]^2 \cdot r(v)$ 这也可以用前缀和计算：$H_2(l,r) = \sum_{i=l}^r \sum_{j=l}^r [A[i]=A[j]] \cdot r(A[i])$，但是，这样复杂度是 $O(n^2)$。

实际上 $H_2 = \sum_{v} cnt[v]^2 \cdot r(v)$ 可以通过预处理每个值的出现位置来算，但更简单的是用另一个随机映射 $r_2(v)$ 计算 $H_2$。

---

如果两个区间完全相同，则 $H_1$ 和 $H_2$ 都相等。

如果相差一对 $(p,q)$，则： $\Delta H_1 = r(p) - r(q)$ $ \Delta H_2 = (cnt_X[p]^2 - cnt_Y[p]^2) r_2(p) + (cnt_X[q]^2 - cnt_Y[q]^2) r_2(q) $ 由于 $cnt_X[p] = cnt_Y[p] + 1$，$cnt_X[q] = cnt_Y[q] - 1$，则： $cnt_X[p]^2 - cnt_Y[p]^2 = 2\,cnt_Y[p] + 1$ $cnt_X[q]^2 - cnt_Y[q]^2 = -2\,cnt_Y[q] + 1$ 所以： $ \Delta H_2 = (2\,cnt_Y[p] + 1) r_2(p) + (-2\,cnt_Y[q] + 1) r_2(q) $ 我们不知道 $cnt_Y[p]$ 和 $cnt_Y[q]$，所以不能直接解。

---

4. 更直接的方法：维护出现次数的哈希

我们维护每个区间中每个数值的出现次数的哈希： $H = \sum_{v} \text{base}^{v} \cdot cnt[v]$ 模大质数。这样如果两个区间频率分布相同，则 $H$ 相同。

如果相差一对 $(p,q)$，则： $H_X - H_Y = \text{base}^p - \text{base}^q$ 我们可以预先计算所有 $\text{base}^v$，然后检查 $H_X - H_Y$ 是否等于某个 $\text{base}^p - \text{base}^q$（$p \neq q$）。

由于 $n,q$ 大，我们可以用哈希表记录所有 $\text{base}^p - \text{base}^q$，但数值范围大时不行。

---

五、最终可行方案

对于子任务 1 ($n,q \le 1000$)，可以直接提取区间排序比较。

对于子任务 2 和 3，我们可以这样做：

• 对序列分块，块大小 $B \approx \sqrt{n}$。
• 对每个块预处理每个值的出现次数（数值需要离散化）。
• 回答询问时，通过块的前缀和快速得到两个区间的频率向量。
• 比较两个频率向量，找出不同的数值，检查是否满足条件。

复杂度：提取频率向量 $O(\sqrt{n})$，比较 $O(\sqrt{n})$（因为不同数值不超过区间长度，但我们可以只记录不同的部分）。

---

六、算法步骤（对大数据）

1. 离散化 $A$。
2. 分块，每块大小 $B=\sqrt{n}$。
3. 预处理 $block[i][v]$ = 前 $i$ 块中值 $v$ 的出现次数。
4. 对询问 $[a,b]$ 和 $[c,d]$：
   • 用块前缀和求出 $freq_X$ 和 $freq_Y$（只记录出现次数变化的项）。
   • 计算差向量 $diff[v] = freq_X[v] - freq_Y[v]$。
   • 收集所有 $diff[v] \neq 0$ 的 $v$。
   • 如果个数为 0 → YES。
   • 如果个数为 2，且差值为 $+1$ 和 $-1$ → YES。
   • 否则 NO。

---

七、代码框架（C++）

// 相似序列
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
const int N = 1e5 + 5, maxv = 1e5;
int _, n, q, rt[N], tot;

inline ull f(ull x) {
    return (((x + 31) * x + 331) * x + 3331) * x + 33331;
}
struct segment {
    int Lc, Rc, cnt;
    ull val;
};
segment tree[N << 5];
inline void pushup(int u) {
    tree[u].cnt = tree[tree[u].Lc].cnt + tree[tree[u].Rc].cnt;
    tree[u].val = tree[tree[u].Lc].val + tree[tree[u].Rc].val;
    return;
}
int build(int L, int R) {
    int u = ++tot;

    if (L == R) {
        tree[u].Lc = 0;
        tree[u].Rc = 0;
        tree[u].cnt = 0;
        tree[u].val = 0;
        return u;
    }

    int mid = (L + R) >> 1;
    tree[u].Lc = build(L, mid);
    tree[u].Rc = build(mid + 1, R);
    pushup(u);
    return u;
}
int posadd(int u, int L, int R, int p) {
    int v = ++tot;
    tree[v] = tree[u];

    if (p == L && R == p) {
        ++tree[v].cnt;
        tree[v].val += f(p);
        return v;
    }

    int mid = (L + R) >> 1;

    if (p <= mid) {
        tree[v].Lc = posadd(tree[u].Lc, L, mid, p);
    }

    if (mid < p) {
        tree[v].Rc = posadd(tree[u].Rc, mid + 1, R, p);
    }

    pushup(v);
    return v;
}
int segsch1(int uL, int uR, int vL, int vR, int L, int R) {
    if (L == R) {
        if (tree[uR].cnt - tree[uL].cnt > tree[vR].cnt - tree[vL].cnt) {
            return (L << 1);
        }

        return ((L << 1) | 1);
    }

    int mid = (L + R) >> 1;

    if (tree[tree[uR].Lc].val - tree[tree[uL].Lc].val != tree[tree[vR].Lc].val - tree[tree[vL].Lc].val) {
        return segsch1(tree[uL].Lc, tree[uR].Lc, tree[vL].Lc, tree[vR].Lc, L, mid);
    }

    return segsch1(tree[uL].Rc, tree[uR].Rc, tree[vL].Rc, tree[vR].Rc, mid + 1, R);
}
int segsch2(int uL, int uR, int vL, int vR, int L, int R) {
    if (L == R) {
        if (tree[uR].cnt - tree[uL].cnt > tree[vR].cnt - tree[vL].cnt) {
            return (L << 1);
        }

        return ((L << 1) | 1);
    }

    int mid = (L + R) >> 1;

    if (tree[tree[uR].Rc].val - tree[tree[uL].Rc].val != tree[tree[vR].Rc].val - tree[tree[vL].Rc].val) {
        return segsch2(tree[uL].Rc, tree[uR].Rc, tree[vL].Rc, tree[vR].Rc, mid + 1, R);
    }

    return segsch2(tree[uL].Lc, tree[uR].Lc, tree[vL].Lc, tree[vR].Lc, L, mid);
}
ull segask(int uL, int uR, int L, int R, int qL, int qR) {
    if (qL <= L && R <= qR) {
        return tree[uR].val - tree[uL].val;
    }

    int mid = (L + R) >> 1;

    if (qR <= mid) {
        return segask(tree[uL].Lc, tree[uR].Lc, L, mid, qL, qR);
    }

    if (mid < qL) {
        return segask(tree[uL].Rc, tree[uR].Rc, mid + 1, R, qL, qR);
    }

    return segask(tree[uL].Lc, tree[uR].Lc, L, mid, qL, qR) + segask(tree[uL].Rc, tree[uR].Rc, mid + 1, R, qL,
            qR);
}

inline ull calc(int L, int R) {
    return tree[rt[R]].val - tree[rt[L - 1]].val;
}
inline int read();
int main() {
    tree[0].Lc = 0;
    tree[0].Rc = 0;
    tree[0].cnt = 0;
    tree[0].val = 0;
    _ = read();

    while (_--) {
        n = read();
        q = read();
        tot = 0;
        build(1, maxv);

        for (int i = 1, j; i <= n; ++i) {
            j = read();
            rt[i] = posadd(rt[i - 1], 1, maxv, j);
        }

        while (q--) {
            int L1 = read();
            int R1 = read();
            int L2 = read();
            int R2 = read();

            if (calc(L1, R1) == calc(L2, R2)) {
                putchar('Y');
                putchar('E');
                putchar('S');
                putchar('\n');
                continue;
            }

            L1 = rt[L1 - 1];
            R1 = rt[R1];
            L2 = rt[L2 - 1];
            R2 = rt[R2];
            int x = segsch1(L1, R1, L2, R2, 1, maxv);
            int y = segsch2(L1, R1, L2, R2, 1, maxv);

            if (!((x & 1) ^ (y & 1))) {
                putchar('N');
                putchar('O');
                putchar('\n');
                continue;
            }

            x >>= 1;
            y >>= 1;

            if (x > y) {
                x ^= y ^= x ^= y;
            }

            ++x;
            --y;

            if (x > y || (segask(L1, R1, 1, maxv, x, y) == 0 && segask(L2, R2, 1, maxv, x, y) == 0)) {
                putchar('Y');
                putchar('E');
                putchar('S');
            } else {
                putchar('N');
                putchar('O');
            }

            putchar('\n');
        }
    }

    return 0;
}
inline int read() {
    int rx = 0;
    char rch = getchar();

    while (rch < '0' || '9' < rch) {
        rch = getchar();
    }

    while ('0' <= rch && rch <= '9') {
        rx = (rx << 3) + (rx << 1) + (rch ^ 48);
        rch = getchar();
    }

    return rx;
}

---

八、总结

本题的关键在于：

1. 理解“相似”的定义：排序后最多一个位置不同。
2. 转化为频率向量的差向量检查。
3. 利用分块快速获取区间频率向量。
4. 检查差向量是否满足恰好两个非零项且差值为 $+1$ 和 $-1$。

该解法可以高效处理 $n,q$ 达到 $10^5$ 的情况。