集合 hash

lkjzyd20 · 2025-03-31 15:46:13 · 算法·理论

Tags: 字符串 hash

集合哈希

集合与序列的不同点在于，集合是无序的，也就是说，序列要求每个位置一一相等，而集合只需要对应的元素出现次数相等即可。

我们匹配哈希主要是匹配是否出现，而集合哈希主要是匹配出现次数。

https://blog.csdn.net/notonlysuccess/article/details/130959107

集合哈希之异或哈希

AT_abc250_e [ABC250E] Prefix Equality

https://www.luogu.com.cn/problem/AT_abc250_e

我们可以先给每一个值赋一个随机数，然后用 O(n) 的时间复杂度来进行去重和维护两个哈希前缀数组。

比如样例：

5
1 2 3 4 5
1 2 2 4 3

可以对于每一个数赋予一个随机数，处理出来

999 678 234 576 134
999 678 678 576 134

然后我们之间统计异或哈希前缀即可。

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
mt19937 rd(time(0));
const int N=2e5+5;
int n,m,a[N],b[N],f1[N],f2[N];
map<int,int> g,mpa,mpb,vis;
main(){
    cin>>n;
    rep(i,1,n)cin>>a[i],vis[a[i]]=1;
    rep(i,1,n)cin>>b[i],vis[b[i]]=1;
    for(auto v:vis)g[v.first]=rd();
    rep(i,1,n)a[i]=g[a[i]],b[i]=g[b[i]];
    rep(i,1,n){
        if(!mpa[a[i]]) f1[i]=f1[i-1]^a[i],mpa[a[i]]=1;
        else f1[i]=f1[i-1];
        if(!mpb[b[i]]) f2[i]=f2[i-1]^b[i],mpb[b[i]]=1;
        else f2[i]=f2[i-1];
    }
    int Q;cin>>Q;
    for(;Q;--Q){
        int x,y;cin>>x>>y;
        if(f1[x]==f2[y])puts("Yes");
        else puts("No");
    }
    return 0;
}

看到代码，很多人肯定觉得不对呀，这不会有很大的冲突吗？

但是，我们由于先赋予了一个独一无二的随机数，所以它的冲突数将会大大减小。

其实这道题还可以使用加法哈希或乘法哈希，但是按照运算来说，异或哈希使用的常数更小，而且冲突也更小。

CF1175F The Number of Subpermutations

https://www.luogu.com.cn/problem/CF1175F

水紫一道，异或哈希模板。观察到一个子区间 [l, r] 如果是一个 1 到 r - l +1 的排列，那么等价于：

我们先预处理出 1\sim n 每一个排列的异或哈希，令它为 f，再处理出一个数列的异或哈希，然后再从前往后找每一个 1 出现的位置，又定义一个类似尺取法的 j，每一次向右扩展，取这个区间的最大值，然后使用前缀哈希判断是否是排列即可。

如果是左边的怎么办呢，我们只需要将这个数列倒转过来，然后再执行前面的操作就可以了。

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=300010;
mt19937_64 rd(time(0));
int n,a[N],g[N],pre[N],f[N],ans;
main(){
    cin>>n;
    rep(i,1,n)cin>>a[i],g[i]=rd(),f[i]=f[i-1]^g[i];
    rep(i,1,n)pre[i]=g[a[i]]^pre[i-1];
    int j=1;
    rep(i,1,n){
        if(a[i]==1)j=1,++ans;
        else{
            j=max(j,a[i]);
            if(i>=j&&(pre[i]^pre[i-j])==f[j])++ans;
        }
    }
    reverse(a+1,a+n+1);
    rep(i,1,n)pre[i]=g[a[i]]^pre[i-1];
    j=1;
    rep(i,1,n){
        if(a[i]==1)j=1;
        else{
            j=max(j,a[i]);
            if(i>=j&&(pre[i]^pre[i-j])==f[j])++ans;
        }
    }
    cout<<ans;
    return 0;
}

CF869E The Untended Antiquity

二维异或哈希和二维树状数组板题。

给定 n\times m 的网格，q 次操作：

将第 [x_1,x_2] 行，第 [y_1,y_2] 列的矩形框起来。
删掉第 [x_1,x_2] 行，第 [y_1,y_2] 列的矩形框，保证该矩形框存在。
询问 (x_1,y_1) 和 (x_2,y_2) 是否连通。

思路：一个很显然的性质，我们查询的两个点只有在围在同样的围墙中才能联通，那我们可以给每个矩形框赋值，然后标记一下，使用二维树状数组维护即可。

但是可能会遇到哈希冲突的情况，所以要使用随机数来减小哈希冲突。

map<tuple<int,int,int,int>,int>vis;
mt19937 rd(time(0));
int f[N][N];
void add(int x,int y,int v){
    for(int i=x;i<=n;i+=i&-i)
        for(int j=y;j<=m;j+=j&-j)
            f[i][j]^=v;
}
int ask(int xx,int yy){
    int ans=0;
    for(int i=xx;i;i-=i&-i)
        for(int j=yy;j;j-=j&-j)
            ans^=f[i][j];
    return ans;
}
void change(int xx1,int yy1,int xx2,int yy2,int v){
    add(xx1,yy1,v);
    add(xx2+1,yy1,v);
    add(xx1,yy2+1,v);
    add(xx2+1,yy2+1,v);
}
void solve(){
    int opt,xx1,yy1,xx2,yy2;
    cin>>opt>>xx1>>yy1>>xx2>>yy2;
    if(opt==1){
        vis[{xx1,yy1,xx2,yy2}]=rd();
        change(xx1,yy1,xx2,yy2,vis[{xx1,yy1,xx2,yy2}]);
    }
    else if(opt==2){
        change(xx1,yy1,xx2,yy2,vis[{xx1,yy1,xx2,yy2}]);
    }
    else {
        int fx=ask(xx1,yy1),fy=ask(xx2,yy2);
        puts(fx==fy?"Yes":"No");
    }
}

集合哈希之 sum 哈希

P8819 [CSP-S 2022] 星战

有一个 n 个点 m 条有向边的图，每条边有可用和不可用两个状态，初始时均为可用边。有 q 个操作：

操作 \tt1：让一条可用边变为不可用边
操作 \tt2：让所有指向这个点的边中，可用边变为不可用边
操作 \tt3：让一条不可用边变为可用边
操作 \tt4：让所有指向这个点的边中，不可用边变为可用边

每次操作之后，判断是否同时满足

条件 \tt1：所有的点出度均为 \tt1。
条件 \tt2：所有的点都满足从该点出发可以走到一个环中。

思路：首先很明显，条件 \tt2 是没有用的，因为你随便构造一个符合条件 \tt1 图，你会发现它满足条件 \tt1。

当然你还可以证明一下，其实这是一棵内向基环树，oi-wiki 上给了详细的定义，~~（反正你考场上也证明不出，还不如直接随便画几个易得）~~。

然后 \tt 1,3 是可以直接 O(1) 解决的，\tt 2,4 可以暴力，这就有 50 分了~~（直接输出 NO 45 分）~~。

我们现在主要来优化 \tt 2,4 操作，我们来维护所有的点它们的出度和，对于每一个点，它们的出度我们给它赋予一个随机值，然后对于每一次操作，直接异或哈希，判断是否原本所有的出度和即可。

这题我使用和异或哈希差不多的 sum 哈希，不知道为什么我的异或哈希过不去。

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=5e5+10;
int n,m,q,a[N];
int tot,ans;
// 定义 to_i.first 表示 i 点出度和，to_i.second 表示最开始 i 点出度和
pair<int,int>to[N];
mt19937 rd(time(0));
void solve(){
    int opt,u,v;
    cin>>opt;
    if(opt==1){
        cin>>u>>v;
        to[v].first-=a[u];//删除 v-u 的出度
        tot-=a[u];//总出度减去 v-u 的出度
    }
    else if(opt==2){
        cin>>u;
        tot-=to[u].first;//总出度减去 u 的出度
        to[u].first=0;//u 的出度清零
    }
    else if(opt==3){
        cin>>u>>v;
        to[v].first+=a[u];//同理
        tot+=a[u];
    }
    else{
        cin>>u;
        tot+=to[u].second-to[u].first;//总出度加上 u 最开始的出度减去现在的出度
        to[u].first=to[u].second;//u 的出度更新为最开始的出度
    }
    puts(tot==ans?"YES":"NO");
}
main(){
    cin>>n>>m;
    rep(i,1,n)a[i]=rd(),ans+=a[i];// 对于每一个点赋随机值
    rep(i,1,m){
        int u,v;
        cin>>u>>v;
        to[v].first+=a[u]; //v 点加上 u-v 点的出度
        to[v].second=to[v].first;
        tot+=a[u]; // 总出度更新
    }
    int Q;cin>>Q;
    for(;Q;--Q)solve();
    return 0;
}