集合 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
#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
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
#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< 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 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 #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 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; }