题目描述

难度分:$1540$

给定两个长度为$n(\leq 2 \times 10^5)$的数组$a$和$b$，以及$q(\leq 2 \times 10^5)$个询问。

每次询问输入$4$个$[1,n]$的整数$l_i,r_i,L_i,R_i$，询问是否可以通过重排$a$的子数组$[l_i,r_i]$使其与$b$的子数组$[L_i,R_i]$相等。可以输出Yes，否则输出No。

输入样例$1$

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

输出样例$1$

Yes
No
No
Yes

输入样例$2$

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

输出样例$2$

Yes
Yes
No
No

算法

哈希

本题的数组值域范围比较大，不能对每个取值求前缀和，但是可以把每个数值哈希到一个非常大的值域。这时候我们希望只要$a$在$[l,r]$上的累加和与$b$在$[L,R]$上的累加和相等，就说明这两个子数组有着相同的元素，每个元素的频数也是相等的。

为了满足这个条件，就需要这个哈希函数能够具有极低的哈希冲突概率，将每个$a$和$b$中的数值映射到一个随机数即可，注意两个数组共用一个映射表。

复杂度分析

时间复杂度

对$a$和$b$两个数组中的元素进行哈希需要遍历两个数组，时间复杂度为$O(n)$。处理$q$个询问，每个询问只需要利用前缀和数组$O(1)$计算出区间和即可判断，所有询问的处理时间为$O(q)$。因此，整个算法的时间复杂度为$O(n+q)$。

空间复杂度

空间开销在于$sa$和$sb$两个前缀和数组，以及映射表$mp$，它们都是线性的，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200010;
int n, q, a[N], b[N];
ULL sa[N], sb[N];

int main() {
    scanf("%d%d", &n, &q);
    unordered_map<int, ULL> mp;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(!mp.count(a[i])) {
            mp[a[i]] = rnd();
        }
        sa[i] = sa[i - 1] + mp[a[i]];
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        if(!mp.count(b[i])) {
            mp[b[i]] = rnd();
        }
        sb[i] = sb[i - 1] + mp[b[i]];
    }
    while(q--) {
        int l, r, L, R;
        scanf("%d%d%d%d", &l, &r, &L, &R);
        if(sa[r] - sa[l - 1] == sb[R] - sb[L - 1]) {
            puts("Yes");
        }else {
            puts("No");
        }
    }
    return 0;
}