一、 xor-hash 功能
这里可以把 sum-hash 和 xor-hash 放在一起对比：
- sum-hash 可以快速判断两个集合对应元素出现次数是否相等。
- xor-hash 可以快速判断两个集合对应元素出现次数奇偶性是否相等。
操作流程：给每个元素赋随机权值 \(key\) ，一个集合的 hash 值为 \(\bigoplus_{x\in S}key_x\) 。
也许有人会问，求 hash 值和直接判断都是 \(\mathcal O(sz)\) 的时间复杂度，优化在哪里？
- 如果要在集合中增删元素，我们可以轻松维护修改后的
hash值。 - 对于静态序列，我们可以用差分前缀和的思想快速计算一个区间的
hash值。 - 如果多次用到同一集合（比如若干集合两两比较一次），我们可以将
hash值预处理。
另一个需要关心的问题是冲突概率。
以 \(n=10^5\) 为例，大多数使用场景我们要维护 \(\mathcal O(n^2)\) 个 hash 值，冲突概率 \(\frac{\mathcal O(n^2)}{2^{64}}\approx 10^{-8}\) ，可以忽略不计。
直接讲非常抽象，下面看一道具体例题。
例1、\(\texttt{CF1175F The Number of Subpermutations}\)
题目描述
给定长为 \(n\) 的序列 \(a\) ，求有多少子序列 \(a_l,\cdots,a_r\) 满足它是 \(1,\cdots,r-l+1\) 的排列。
数据范围
- \(1\le n\le 3\cdot 10^5\) 。
- \(1\le a_i\le n\) 。
时间限制 \(\texttt{2s}\) ，空间限制 \(\texttt{256MB}\) 。
分析
如果枚举 \(l,r\) ，再暴力判断是否符合要求，时间复杂度 \(\mathcal O(n^3)\) 。
预处理 \(s_i=\bigoplus_{j=1}^ikey_{a_j}\) ，我们可以在 \(\mathcal O(1)\) 的时间内判断一个区间是否符合要求，时间复杂度 \(\mathcal O(n^2)\) 。
如果要做到 \(\mathcal O(n)\) ，我们至多只能枚举一侧端点，然后将另一侧端点算出来。
枚举 \(1\) 在序列中出现的位置 \(x\) ，统计所有跨过 \(x\) 的区间 \([l,r]\) 的贡献。
对最大值在 \(x\) 左边还是右边分类讨论。如果在左边，即 \(len=\max\limits_{l\le i\le r}a_i=\max\limits_{l\le i\le x}a_i\) ，枚举 \(l\) 时可以直接算出 \(r=l+len-1\) ，然后 \(\mathcal O(1)\) 判断这个区间是否符合要求即可。
时间复杂度 \(\mathcal O(n)\) ，注意上述方法也侧面证明答案不超过 \(2n\) 。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=3e5+5;
int n,res;
int a[maxn];
ull s[maxn],t[maxn],v[maxn];
mt19937_64 rnd(time(0));
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) v[i]=rnd(),t[i]=t[i-1]^v[i];
for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]^v[a[i]];
for(int i=1;i<=n;i++)
{
if(a[i]!=1) continue;
res++;
for(int l=i-1,len=0;l&&a[l]!=1;l--) len=max(len,a[l]),res+=l+len-1<=n&&(s[l+len-1]^s[l-1])==t[len];
for(int r=i+1,len=0;r<=n&&a[r]!=1;r++) len=max(len,a[r]),res+=r-len+1>=1&&(s[r]^s[r-len])==t[len];
}
printf("%d\n",res);
return 0;
}
通过这道题可以看出， hash 值相等只是集合相等的必要条件，有时我们也会维护集合最大值、集合元素出现次数等信息进行辅助判断。
sum-hash 能做的题和 xor-hash 能做的题绝大部分在二者交集中，本文重点讲 xor-hash ，读者可以自行思考 sum-hash 是否可行。
二、相关例题
例2、\(\texttt{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)\) 是否连通。
数据范围
- \(1\le n,m\le 2500\) 。
- \(1\le q\le 10^5\) 。
时间限制 \(\texttt{2s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
给每个矩形框赋随机权值 \(key\) 。
矩形加矩形异或和，二维树状数组维护。
时间复杂度 \(\mathcal O(q\log n\log m)\) 。
#include<bits/stdc++.h>
#define y1 y_1
#define ull unsigned long long
using namespace std;
int m,n,q,op,x1,x2,y1,y2;
ull c[2505][2505];
map<array<int,4>,ull> h;
mt19937_64 rnd(time(0));
void add(int x,int y,ull v)
{
for(int i=x;i<=n;i+=i&-i)
for(int j=y;j<=m;j+=j&-j)
c[i][j]^=v;
}
ull sum(int x,int y)
{
ull res=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
res^=c[i][j];
return res;
}
int main()
{
for(scanf("%d%d%d",&n,&m,&q);q--;)
{
scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
if(op==1)
{
ull v=rnd();
add(x1,y1,v),add(x2+1,y1,v),add(x1,y2+1,v),add(x2+1,y2+1,v),h[{x1,y1,x2,y2}]=v;
}
if(op==2)
{
ull v=h[{x1,y1,x2,y2}];
add(x1,y1,v),add(x2+1,y1,v),add(x1,y2+1,v),add(x2+1,y2+1,v);
}
if(op==3) printf(sum(x1,y1)==sum(x2,y2)?"Yes\n":"No\n");
}
return 0;
}
例3、\(\texttt{CF1622F Quadratic Set}\)
题目描述
若 \(\prod_{k\in S}k!\) 是完全平方数，则称 \(S\) 为平方集合。
求最大的 \(S\subseteq\{1,2,\cdots,n\}\) ，使得 \(S\) 为平方集合，构造方案。
数据范围
- \(1\le n\le 10^6\) 。
时间限制 \(\texttt{4s}\) ，空间限制 \(\texttt{256MB}\) 。
分析
本题最重要的一步是观察到 \(|S|\ge n-3\) 。
注意到：
\[\prod_{i=1}^{2k}i!=2^kk!\left(\prod_{i=1}^k(2i-1)!\right)^2\\ \]如果 \(n=2k+1\) ，先扔掉 \(n\) 。
扔掉 \(k\) 。如果 \(k\) 为偶数，再扔掉 \(2\) 。
接下来的任务是依次判断 \(|S|\) 能否等于 \(n,n-1,n-2\) 。
给每个质因子 \(p\) 赋随机权值 \(key\) ，记 \(val_k\) 为 \(k!\) 的所有质因子的权值异或和， \(M=\bigoplus_{k=1}^nval_k\) 。
若 \(M=0\) ，则答案为 \(n\) 。
若 \(\exist val_k=M\) ，则答案为 \(n-1\) 。
否则枚举 \(k\) ，查找 \(M\oplus val_k\) 是否出现过。若是，则答案为 \(n-2\) ，否则答案为 \(n-3\) 。
时间复杂度可以做到 \(\mathcal O(n)\) ，不过博主为偷懒直接暴力质因数分解了。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=1e6+5;
int n;
ull m,k[maxn],v[maxn];
unordered_map<ull,int> vis;
mt19937_64 rnd(time(0));
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) v[i]=rnd();
for(int i=1;i<=n;i++)
{
int x=i;
for(int j=2;j*j<=n;j++) while(x%j==0) x/=j,k[i]^=v[j];
if(x!=1) k[i]^=v[x];
k[i]^=k[i-1],m^=k[i],vis[k[i]]=i;
}
if(!m)
{
printf("%d\n",n);
for(int i=1;i<=n;i++) printf("%d ",i);
return putchar('\n'),0;
}
for(int i=1;i<=n;i++)
{
if(k[i]!=m) continue;
printf("%d\n",n-1);
for(int j=1;j<=n;j++) if(j!=i) printf("%d ",j);
return putchar('\n'),0;
}
for(int i=1;i<=n;i++)
{
if(!vis[k[i]^m]) continue;
printf("%d\n",n-2);
for(int j=1,x=vis[k[i]^m];j<=n;j++) if(j!=i&&j!=x) printf("%d ",j);
return putchar('\n'),0;
}
printf("%d\n",n-3);
for(int j=1;j<=n;j++) if(j!=2&&j!=n/2&&j!=n) printf("%d ",j);
return putchar('\n'),0;
}
总结
- 完全平方数是包装奇偶性的一种常见方法。
例4、\(\texttt{CF1418G Three Occurrences}\)
题目描述
给定长为 \(n\) 的序列 \(a\) ，求有多少子序列 \(a_l,\cdots,a_r\) 满足所有出现过的数都恰好出现 \(3\) 次。
数据范围
- \(1\le n\le 5\cdot 10^5\) 。
- \(1\le a_i\le n\) 。
时间限制 \(\texttt{5s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
将恰好出现 \(3\) 次拆成下面两个条件：
- 出现次数为 \(3\) 的倍数。
- 出现次数 \(\le 3\) 。
对于第一个条件，将 \(x\) 在原序列中第 \(3k+1\) 次出现赋值 \(u_x\) ，第 \(3k+2\) 次出现赋值 \(v_x\) ，第 \(3k+3\) 次出现赋值 \(u_x\oplus v_x\) 。
这样对于任意连续 \(3\) 次出现 \(x\) ，一定是 \(u_x,v_x,u_x\oplus v_x\) 各贡献一次。
第二个条件可以双指针解决，时间复杂度 \(\mathcal O(n)\) 。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=5e5+5;
int n;
long long res;
int a[maxn],cnt[maxn];
ull s[maxn],u[maxn],v[maxn];
unordered_map<ull,int> h;
mt19937_64 rnd(time(0));
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) u[i]=rnd(),v[i]=rnd();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]),cnt[a[i]]++;
if(cnt[a[i]]%3==1) s[i]=s[i-1]^u[a[i]];
else if(cnt[a[i]]%3==2) s[i]=s[i-1]^v[a[i]];
else s[i]=s[i-1]^u[a[i]]^v[a[i]];
}
memset(cnt+1,0,4*n),h[s[0]]=1;
for(int l=1,r=1;r<=n;r++)
{
for(cnt[a[r]]++;cnt[a[r]]>3;) h[s[l-1]]--,cnt[a[l++]]--;
res+=h[s[r]]++;
}
printf("%lld\n",res);
return 0;
}
例5、\(\texttt{P8819 [CSP-S 2022] 星战}\)
这里有 sum-hash 的题解，和 xor-hash 本质相同。
例6、\(\texttt{P10785 [NOI2024] 集合}\)
题目描述
定义基本集合为大小为 \(3\) ，元素在 \(1\sim m\) 内的集合。
定义基本序列为由基本集合构成的序列。
对于排列 \(p\) 和集合 \(S\) ，定义 \(f_p(S)=\{p_x\mid x\in S\}\) 。
对两个长度为 \(k\) 的基本序列 \(A,B\) ，定义 \(A\) 和 \(B\) 等价当且仅当存在排列 \(p\) ，使得 \(\forall 1\le i\le k,f_p(A_i)=B_i\) 。
给定长为 \(n\) 的基本序列 \(A,B\) 。 \(q\) 次询问，每次给定 \(l,r\) ，查询基本序列 \(\{A_l,\cdots,A_r\}\) 和 \(\{B_l,\cdots,B_r\}\) 是否等价。
数据范围
- \(1\le n\le 2\cdot 10^5,3\le m\le 6\cdot 10^5,1\le q\le 10^6\) 。
- \(1\le l\le r\le n\) 。
时间限制 \(\texttt{1s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
对于 \(m\le 5\) 的测试点，枚举排列，对每个 \(k\) 判定 \(A_k\) 和 \(B_k\) 是否等价，对每个 \(l\) 维护最大的 \(r\) ，时间复杂度 \(\mathcal O(120n+q)\) ，可以获得 \(60\) 分。
正解需要跳出关于排列的思维模式。从元素的角度来考虑，对 \(\forall 1\le x\le m\) ，设它在 \(A\) 和 \(B\) 中出现下标构成的集合分别为 \(S_x\) 和 \(T_x\) 。则 \(A\) 和 \(B\) 等价当且仅当 \(\{S_1,\cdots,S_m\}=\{T_1,\cdots,T_m\}\) 。
第一次哈希将 \(S_x,T_x\) 映射成一个数， sum-hash 或 xor-hash 均可，第二次哈希判断数集相等，只能用 sum-hash 。
至此已经可以处理单组询问。由于 sum-hash 和 xor-hash 都可以轻松实现增删元素，双指针对每个 \(l\) 维护最远的 \(r\) 即可，时间复杂度 \(\mathcal O(n+m+q)\) 。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=6e5+5;
int l,m,n,q,r;
int res[maxn];
ull s1,s2,v[maxn],w1[maxn],w2[maxn];
array<int,3> a[maxn],b[maxn];
mt19937_64 rnd(time(0));
ull code(ull x)
{
x^=x>>7,x^=x<<11,x^=x>>13;
return x;
}
void add(ull &s,ull *w,int i,array<int,3> p)
{
for(auto x:p) s-=code(w[x]),w[x]^=v[i],s+=code(w[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
for(int i=1;i<=n;i++) scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);
for(int i=1;i<=n;i++) v[i]=rnd();
for(int l=1,r=0;l<=n;l++)
{
while(r<=n&&s1==s2) if(++r<=n) add(s1,w1,r,a[r]),add(s2,w2,r,b[r]);
add(s1,w1,l,a[l]),add(s2,w2,l,b[l]),res[l]=r-1;
}
while(q--)
{
scanf("%d%d",&l,&r);
printf(r<=res[l]?"Yes\n":"No\n");
}
return 0;
}