浅谈处理哈希问题的一类方法-线段树维护哈希

简介/概括哈希是一种常用的算法。我们在oi中使用哈希的主要目的是将难以直接处理、维护、比较的对象映射到范围小/便于维护/便于处理/便于比较的对象上。映射的方式是哈希函数 $hash(x)$,设计哈希函数时会考虑对象的特性并尽可能避免冲突。通常我们时常会把研究对象映射到整数上这样就会出现溢出的问题解决方法无非就两种1.自然溢出就是不管它让它自行溢出根据溢出值来比较。仅限于long long类型。2.双哈希同时设计两种不同哈希函数进行维护。可大幅提升准确率减少冲突概率。字符串哈希哈希里面比较常见的一种就是把一个字符串看成一个 $n$ 进制数把字符串弄成一个类似键值的东西。对字符串作哈希后可以进行高效的比较、取子串等操作有时还会用线段树去维护它一般带修。总而言之字符串哈希是处理字符串问题的一种常见思路。CF580E Kefa and Watch题意描述维护一种由数字构成字符数组可以执行以下操作:1.格式l r c,将l~r都赋值为$c$2.格式: l r d,询问l~r是否有长度为$d$的循环节solve使用线段树去维护这个字符串哈希值。关于怎样判断一个字符串 $s$ 有长度为 $d$ 的循环节可以证明字符串 $s$ 有长度为 $d$ 的循环节等价于 $s[1...n-d]s[d1...n]$ ($s[l,r]$ 表示 $s$ 从 $l$ 到$r$ 的子串)。使用线段树维护子串的哈希值就可以完成以上比较了。code#includeiostream #includecstdio #includestring #define int long long #define N 1000007 using namespace std; struct Sigement{ string s; int mod,pw[100007],seed,note[100007]; struct Tr{ int tag,value; }tree[500007]; void init(){ int lens.size(); pw[0]1; note[0]1; for(int i1;ilen4;i){ pw[i]pw[i-1]*seed%mod; note[i]note[i-1]pw[i]; note[i]%mod; } } void pushup(int l,int r,int pos){ int mid(lr)/2; tree[pos].valuetree[pos*2].value*pw[r-mid]%modtree[pos*21].value; tree[pos].value%mod; } void pushdown(int k,int l,int r,int pos){ int mid(lr)/2; tree[pos*2].tagk; tree[pos*2].value(k0)*note[mid-l]%mod; tree[pos*21].tagk; tree[pos*21].value(k0)*note[r-mid-1]%mod; tree[pos].tag-1; } void build(int l,int r,int cnt){ tree[cnt].tag-1; if(lr){ tree[cnt].values[l]; return ; } int mid(lr)/2; build(l,mid,cnt*2); build(mid1,r,cnt*21); pushup(l,r,cnt); } void update(int l,int r,int L,int R,int k,int cnt){ if(LlrR){ tree[cnt].tagk; tree[cnt].value(k0)*note[r-l]%mod; return ; } int mid(lr)/2; if(tree[cnt].tag!-1){ pushdown(tree[cnt].tag,l,r,cnt); } if(Lmid){ update(l,mid,L,R,k,cnt*2); } if(Rmid){ update(mid1,r,L,R,k,cnt*21); } pushup(l,r,cnt); } int query(int l,int r,int L,int R,int cnt){ if(LlrR){ return tree[cnt].value; } int mid(lr)/2,ans0; if(tree[cnt].tag!-1){ pushdown(tree[cnt].tag,l,r,cnt); } if(Lmid){ ansquery(l,mid,L,R,cnt*2); } if(Rmid){ ansans*pw[min(r,R)-mid]%modquery(mid1,r,L,R,cnt*21); ans%mod; } return ans; } }tr1,tr2; signed main(){ int n,m,k; cinnmk; cintr1.s; tr1.seed128; tr1.mod998244353; tr1.init(); tr1.build(0,n-1,1); tr2.str1.s; tr2.seed131; tr2.mod1e97; tr2.init(); tr2.build(0,n-1,1); for(int i1;imk;i){ int op; cinop; if(op1){ int l,r,c; cinlrc; tr1.update(0,n-1,l-1,r-1,c,1); tr2.update(0,n-1,l-1,r-1,c,1); }else{ int l,r,d; cinlrd; l--; r--; if(r-l1d){ coutYES\n; } else if(tr1.query(0,n-1,ld,r,1)tr1.query(0,n-1,l,r-d,1)tr2.query(0,n-1,ld,r,1)tr2.query(0,n-1,l,r-d,1)){ coutYES\n; }else coutNO\n; } } return 0; }P2757 [国家集训队] 等差子序列题意描述给一个数组问它里面存不存在等差数列。solve这题比较抽象它卡常。首先显然存在等差子序列等价于存在长度为 3 的等差子序列。这大大降低了问题的难度。因为很容易可以想到枚举中间项看看存不存在一个 $k$,使得在当前数两边分别存在等于 $a_ik$ 与 $a_i-k$ 的数。时间复杂度 $O(n^2)$。接下来就是要优化上述过程。正难则反我们可以考虑什么情况下无解。显然假如对于一个 $a_i$$a_i-k$ 与 $a_ik$ 都在它的左边这就是无解的。其实我们可以整一个桶把便利过的 $a_i$ 都标记一下再沿当前位置对折看看重合的两个数是否都相等若是对于这个中项无解否则有解。这么说可能比较抽象其实就是看以 $a_i$ 为中心长度为 $2k-1$ 的 01 串是否是回文串。( $k$ 指最大的合法的 $k$ )我们可以用权值线段树去维护这个字符串哈希同时维护正序倒序哈希就可以判回文了。code#includebits/stdc.h using namespace std; int t,n,a[500005]; int mod998244353,PW2; int hash1[2000005],hash2[2000005],pw[500005]; void pushup(int now,int l,int r){ int mid(lr)/2; hash1[now](hash1[now*2]*1LL*pw[r-mid]%modhash1[now*21])%mod; hash2[now](hash2[now*2]hash2[now*21]*1LL*pw[mid-l1]%mod)%mod; } void add(int now,int l,int r,int x){ if(lr){ hash1[now]hash2[now]1; }else{ int mid(lr)/2; if(xmid) add(now*2,l,mid,x); if(xmid) add(now*21,mid1,r,x); pushup(now,l,r); } } int query1(int now,int l,int r,int L,int R){ if(LlrR){ return hash1[now]; }else{ int mid(lr)/2; int ans0; if(Rmid) return query1(now*2,l,mid,L,R); if(Lmid) return query1(now*21,mid1,r,L,R); ansquery1(now*2,l,mid,L,R); ans(ans*1LL*pw[min(r,R)-mid]%modquery1(now*21,mid1,r,L,R))%mod; return ans; } } int query2(int now,int l,int r,int L,int R){ if(LlrR){ return hash2[now]; }else{ int mid(lr)/2; int ans0; if(Rmid) return query2(now*2,l,mid,L,R); if(Lmid) return query2(now*21,mid1,r,L,R); ansquery2(now*21,mid1,r,L,R); ans(ans*1LL*pw[mid-max(l,L)1]%modquery2(now*2,l,mid,L,R))%mod; return ans; } } void build(int x,int l,int r){ if(lr){ hash1[x]0; hash2[x]0; return ; } int mid(lr)/2; build(x*2,l,mid); build(x*21,mid1,r); pushup(x,l,r); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cint; pw[0]1; for(int i1;i500002;i){ pw[i]pw[i-1]*1LL*PW%mod; } while(t--){ cinn; build(1,1,n); for(int i1;in;i){ cina[i]; } int flg0; for(int i1;in;i){ add(1,1,n,a[i]); int lenmin(n-a[i]1,a[i]); if(query1(1,1,n,a[i]-len1,a[i])!query2(1,1,n,a[i],a[i]len-1)){ flg1; break; } } if(flg){ coutY\n; }else coutN\n; } return 0; }其它类型的哈希有时还会去用哈希维护一个难以直接维护、操作、比较的数列或集合等。这时就需要根据这个维护对象的特质构建哈希函数有时还会套上数据结构。真是挺恶心的。蒟蒻目前常见到的两种套路(dalao勿喷):1.考虑顺序的数列比如有个有序数列 $a$ , $|a|n$比较两个数列我们可以使用以下哈希函数$$hash(a)\sum_{i1}{n}baseia_i$$2.无序性集合有个集合 $A$判断两个集合是否相同时可以使用以下哈希函数$$hash(A)\sum_{x \in A}base^x$$P6688 可重集这道题和上道题差不多难就是不卡常好许多。就是把每个数当做幂数这样区间的 hash 值就和数字顺序无关了。如对于数列 $x$哈希方式为$$ hash(x)\sum_{i1}nbase\mod p$$日常线段树维护一下。维护两个量一个是哈希值因为要区间加上 $k$再维护最小值。code#includeiostream #includecstdio using namespace std; int n,q,a[1000007]; const int mod1e97,base2; int pw[1000007],sum[4000007],minn[4000007]; void pushup(int now){ minn[now]min(minn[now*2],minn[now*21]); sum[now](sum[now*2]sum[now*21])%mod; } void build(int now,int l,int r){ if(lr){ sum[now]pw[a[l]]; minn[now]a[l]; return ; } int mid(lr)/2; build(now*2,l,mid); build(now*21,mid1,r); pushup(now); } void upd(int now,int l,int r,int x,int y){ if(lr){ sum[now]pw[y]; minn[now]y; return ; } int mid(lr)/2; if(xmid) upd(now*2,l,mid,x,y); else upd(now*21,mid1,r,x,y); pushup(now); } long long Qs(int now,int l,int r,int L,int R){ if(LlrR){ return sum[now]; } int mid(lr)/2; long long ans0; if(Lmid) ans(ansQs(now*2,l,mid,L,R))%mod; if(Rmid) ans(ansQs(now*21,mid1,r,L,R))%mod; return ans; } int Qm(int now,int l,int r,int L,int R){ if(LlrR){ return minn[now]; } int mid(lr)/2; int ans0x3f3f3f3f; if(Lmid) ansmin(ans,Qm(now*2,l,mid,L,R)); if(Rmid) ansmin(ans,Qm(now*21,mid1,r,L,R)); return ans; } void pri(int now,int l,int r){ if(lr){ coutminn[now] ; return ; } int mid(lr)/2; pri(now*2,l,mid); pri(now*21,mid1,r); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); pw[0]1; for(int i1;i1000000;i){ pw[i]pw[i-1]*1LL*base%mod; } cinnq; for(int i1;in;i){ cina[i]; } build(1,1,n); while(q--){ int op; cinop; if(op0){ int x,y; cinxy; upd(1,1,n,x,y); }else{ int l1,r1,l2,r2; cinl1r1l2r2; long long ans1,ans2,fi1,fi2; ans1Qs(1,1,n,l1,r1); ans2Qs(1,1,n,l2,r2); fi1Qm(1,1,n,l1,r1); fi2Qm(1,1,n,l2,r2); if(fi1fi2){ swap(ans1,ans2); swap(fi1,fi2); } if(ans1*1LL*pw[fi2-fi1]%modans2){ coutYES\n; }else coutNO\n; } } return 0; }