6.线段树维护哈希.docx

本节内容属于算法提高知识，由专属金牌选手录制，由于视频时长有限，所以视频中例题讲解主要以C++为主讲解，大家可正常学习。算法思维是共通的，例题的其他语言解题代码，我们也在下方提供了，大家可以参考哦～

线段树维护哈希

C++

#includebits/stdc++.h

usingnamespacestd;

usingLL=longlong;

constintN=2e5+5;

intn,q;

intmod1=998244353,mod2bas=233;

LLbs1[N],bs2[N];

structasdf{

inth1,h2,len;

asdfoperator+(constasdfc)const

{

return{int((h1*bs1[c.len]+c.h1)%mod1),int((h2*bs2[c.len]+c.h2)%mod2),len+c.len};

}

booloperator==(constasdfc)const

{

return(h1==c.h1h2==c.h2len==c.len);

}

}s[N2];

stringa;

asdfbuild(intl,intr,intrt)

{

if(l==r)returns[rt]={a[l],a[l],1};

returns[rt]=build(l,(l+r)/2,rt*2)+build((l+r)/2+1,r,rt*2+1);

}

asdfquery(intl,intr,intrt,intx,inty)

{

if(x=lr=y)returns[rt];

if(y=(l+r)/2)returnquery(l,(l+r)/2,rt*2,x,y);

if(x(l+r)/2)returnquery((l+r)/2+1,r,rt*2+1,x,y);

returnquery(l,(l+r)/2,rt*2,x,y)+query((l+r)/2+1,r,rt*2+1,x,y);

}

asdfmodify(intl,intr,intrt,intad,charch)

{

if(l==r)returns[rt]={ch,ch,1};

if(ad=(l+r)/2)returns[rt]=modify(l,(l+r)/2,rt*2,ad,ch)+s[rt*2+1];

returns[rt]=s[rt*2]+modify((l+r)/2+1,r,rt*2+1,ad,ch);

}

intmain()

{

cin.tie(0);

cout.tie(0);

ios::sync_with_stdio(0);

cinna;

bs1[0]=bs2[0]=1;

for(inti=1;i=n;++i)

{

bs1[i]=bs1[i-1]*bas%mod1;

bs2[i]=bs2[i-1]*bas%mod2;

}

a=!+a;

build(1,n,1);

intopt,l1,r1,l2,r2,ad;

charch;

asdfx,y;

for(cinq;q--;)

{

if(cinopt,opt==1)

{

cinadch;

modify(1,n,1,ad,ch);

}

else

{

cinl1r1l2r2;

x=query(1,n,1,l1,r1);

y=query(1,n,1,l2,r2);

if(x==y)coutYES\n;

elsecoutNO\n;

}

}

return0;

}

Java

importjava.io.*;

importjava.util.*;

importjava.io.BufferedReader;

importjava.io.IOException;

importjava.io.InputStreamReader;

importjava.io.PrintWriter;

importjava.util.StringToken