【BZOJ2555】SubString

算是学会sam了吧……

原题：

懒得写背景了，给你一个字符串init，要求你支持两个操作

    (1):在当前字符串的后面插入一个字符串

    (2):询问字符串s在当前字符串中出现了几次？(作为连续子串)

    你必须在线支持这些操作。
字符串最终长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000

恩

因为sam添点本来就是动态的所以动态往后连接串就不用管了

问题是维护right集的大小，如果新添了一个点np那么从np一直到sam的根right集的大小都会+1对吧

暴力修改即可？以前是可以的，现在新添一组数据卡掉了……

那咋办，动态树上进行路径修改，lct口贝

值得注意的是修改的路径是当前点到原树根的，lct上修改的时候需要把原树根钦定为lct的根然后再access再splay再修改

注意询问串可能比插入串和起始串长，如果共用一个字符数组的话要开成3e6……

注意题中给出的强制在线函数中mask是个局部变量……也就是说转码的时候mask不会变，询问的时候才会变……

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int qwq=;

 int m;  char s[],t[];  int n;

 int nxt[][],fth[],mx[],sz[],lst=,npt=;

 int c[][],fa[],v[],dt[],rvs[];

 int stck[],tp=;

 inline bool isrt(int x){  return (c[fa[x]][]!=x)&(c[fa[x]][]!=x);}

 inline void pshd(int x){

     v[c[x][]]+=dt[x],dt[c[x][]]+=dt[x];

     v[c[x][]]+=dt[x],dt[c[x][]]+=dt[x];

     dt[x]=;

     if(!rvs[x])  return ;

     rvs[c[x][]]^=,rvs[c[x][]]^=,rvs[x]=;

     swap(c[x][],c[x][]);

 }

 inline void rtt(int x){

     int y=fa[x],z=fa[fa[x]],l,r;

     r=(c[y][]==x);  l=r^;

     if(!isrt(y))  c[z][c[z][]==y]=x;

     fa[x]=z,fa[y]=x,fa[c[x][r]]=y;

     c[y][l]=c[x][r],c[x][r]=y;

 }

 inline void sply(int x){

     stck[tp=]=x;

     for(int i=x;!isrt(i);i=fa[i])  stck[++tp]=fa[i];

     while(tp)  pshd(stck[tp--]);

     while(!isrt(x)){

         if(!isrt(fa[x]))  rtt((c[fa[x]][]==x)^(c[fa[fa[x]]][]==fa[x])?x:fa[x]);

         rtt(x);

     }

 }

 inline void accs(int x){  for(int i=;x;sply(x),c[x][]=i,x=fa[i=x]);}

 inline void qdrt(int x){  accs(x),sply(x),rvs[x]^=;}

 inline void lk(int x,int y){  qdrt(x),fa[x]=y,sply(x);}

 inline void ct(int x,int y){  qdrt(x),accs(y),sply(y),fa[x]=c[y][]=;}

 inline void bf(int x,int y){  qdrt(),accs(x),sply(x),v[x]+=y,dt[x]+=y;}

 inline int sch(int x){  sply(x);  return v[x];}

 void rds(){

     scanf("%s",s);  n=strlen(s);  int tmp=qwq;

     for(int i=;i<n;++i){

         tmp=(tmp*+i)%n;

         swap(s[i],s[tmp]);

     }

 }

 /*void ist(int x){

     int p=lst,np=lst=++npt;

     mx[np]=mx[p]+1;  sz[np]=0;

     while((!nxt[p][x])&((!p)^1))  nxt[p][x]=np,p=fth[p];

     if(!p)  fth[np]=1;

     else{

         int q=nxt[p][x];

         if(mx[q]==mx[p]+1)  fth[np]=q;

         else{

             int nq=++npt;  mx[nq]=mx[p]+1;  sz[nq]=sz[q];

             memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));

             fth[nq]=fth[q],fth[q]=fth[np]=nq;

             while(nxt[p][x]==q)  nxt[p][x]=nq,p=fth[p];

         }

     }

     while(np)  ++sz[np],np=fth[np];

 }*/

 void ist(int x){

     int p=lst,np=lst=++npt;

     mx[np]=mx[p]+;  v[np]=;

     while((!nxt[p][x])&((!p)^))  nxt[p][x]=np,p=fth[p];

     if(!p)  fth[np]=,lk(np,);

     else{

         int q=nxt[p][x];

         if(mx[q]==mx[p]+)  fth[np]=q,lk(np,q);

         else{

             int nq=++npt;  mx[nq]=mx[p]+;  v[nq]=sch(q);

             memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));

             ct(q,fth[q]),lk(nq,fth[q]),lk(q,nq),lk(np,nq);

             fth[nq]=fth[q],fth[q]=fth[np]=nq;

             while(nxt[p][x]==q)  nxt[p][x]=nq,p=fth[p];

         }

     }

     bf(np,);

     //cout<<sch(5)<<" "<<fth[3]<<endl;

 }

 int qr(){

     int tmp=;

     for(int i=;i<n;++i)  tmp=nxt[tmp][s[i]-'A'];

     return tmp?sch(tmp):;

 }

 int main(){freopen("ddd.in","r",stdin);

     cin>>m;  scanf("%s",s);  n=strlen(s);

     for(int i=;i<n;++i)  ist(s[i]-'A');

     while(m--){

         scanf("%s",t);  rds();

         if(t[]=='A')  for(int i=;i<n;++i)  ist(s[i]-'A');

         else{  int tmp=qr();  qwq^=tmp;  printf("%d\n",tmp);}

     }

     return ;

 }

巴特西

【BZOJ2555】SubString

最新文章

热门文章