随机化哈希

zc-study-xcu / 2024-08-27 / 原文

算法介绍

我们知道哈希是一种判断多重集是否相等的算法，即将多重集映射为一个数，以数的相等代多重集的相等，这个数称作哈希值。但是多重集是不考虑顺序的，因此，为了确保正确性，需要在映射的过程中引入随机性。即对每个多重集中的元素随机赋一个权值。代码实现上，通常可以取 m = 2^64，使用 unsigned long long 进行计算，并使用 C++ 中的伪随机数生成器 std::mt19937_64 来生成随机数。

例题：F - Rearrange Query

题意：给定两个长度为 $N$ 的整数序列 $A$ 和 $B$，依次处理 $Q$ 个询问，每个询问分别给出 $A$ 和 $B$ 的一个多重子集，判断是否相等。

思路：分别将两个多重子集随机化哈希，然后判断值是否相等。

代码：

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
ull a[N], b[N], n, q, g[N];
void solve()
{
    int T = 1;
    // cin>>T;
    while (T--)
    {
        mt19937_64 rng(time(0));
        cin >> n >> q;
        for (int i = 1; i <= n; i ++)
        {
            g[i] = rng();
            cin >> a[i];
        }
        for (int i = 1; i <= n; i ++)
        {
            cin >> b[i];
        }
        for (int i = 1; i <= n; i ++)
        {
            a[i] = a[i - 1] + g[a[i]];
            b[i] = b[i - 1] + g[b[i]];
        }
        for (int i = 1, l, r, L, R; i <= q; i ++)
        {
            cin >> l >> r >> L >> R;
            if(a[r]-a[l-1] == b[R] - b[L-1])
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }
}
signed main()
{
    ios;
    solve();
    return 0;
}