Atcoder [ABC367F] Rearrange Query 题解

简要题意

给定两个长度为 \(N\) 的序列 \(A\) 和 \(B\)。
有 \(Q\) 个查询，每个查询给定 \(l,r,L,R\)，其中 \(l \leq r, L \leq R\)，要求判断 \(A\) 的第 \(l\) 项到第 \(r\) 项构成的集合与 \(B\) 的第 \(L\) 项到第 \(R\) 项构成的集合是否相等。

题解

显然两个相等的集合所有元素之和相等，但是如果直接判断和肯定是不行的，有反例 1 2 2 3 和 2 2 2 2，于是我们考虑类似哈希的做法，把每个数映射到随机的值，然后判断映射值的和是否相等。

这里我们可以用 map 维护映射的随机值，读入时即判断该数是否映射，若没有则赋一个随机值加到 map 中，这里随机值对 \(1000000\) 取模。然后预处理映射的随机值的前缀和，询问时 \(\mathcal{O(1)}\) 减一下判断即可。

代码见下

#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = a; i <= b; i++)
using namespace std;
const int N = 200005;
int n, q, a[N], b[N];
int s[N], s2[N];
map<int, int> mp;
signed main() {
    srand(time(0));
    cin >> n >> q;
    _for(i, 1, n) {
        cin >> a[i];
        if(mp.find(a[i]) == mp.end()) mp[a[i]] = rand() % 1000000;
        s[i] = s[i - 1] + mp[a[i]];
    }
    _for(i, 1, n) {
        cin >> b[i];
        if(mp.find(b[i]) == mp.end()) mp[b[i]] = rand() % 1000000;
        s2[i] = s2[i - 1] + mp[b[i]];
    }
    while(q--) {
        int l, r, L, R; cin >> l >> r >> L >> R;
        if(s[r] - s[l - 1] == s2[R] - s2[L - 1]) puts("Yes");
        else puts("No");
    }
    return 0;
}