首页 > 代码库 > 【BZOJ2555】SubString

【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不会变,询问的时候才会变……

代码:

技术分享
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 using namespace std;
  7 int qwq=0;
  8 int m;  char s[3100000],t[10];  int n;
  9 int nxt[1210000][26],fth[1210000],mx[1210000],sz[1210000],lst=1,npt=1;
 10 int c[1210000][2],fa[1210000],v[1210000],dt[1210000],rvs[1210000];
 11 int stck[1210000],tp=0;
 12 inline bool isrt(int x){  return (c[fa[x]][0]!=x)&(c[fa[x]][1]!=x);}
 13 inline void pshd(int x){
 14     v[c[x][0]]+=dt[x],dt[c[x][0]]+=dt[x];
 15     v[c[x][1]]+=dt[x],dt[c[x][1]]+=dt[x];
 16     dt[x]=0;
 17     if(!rvs[x])  return ;
 18     rvs[c[x][0]]^=1,rvs[c[x][1]]^=1,rvs[x]=0;
 19     swap(c[x][0],c[x][1]);
 20 }
 21 inline void rtt(int x){
 22     int y=fa[x],z=fa[fa[x]],l,r;
 23     r=(c[y][0]==x);  l=r^1;
 24     if(!isrt(y))  c[z][c[z][1]==y]=x;
 25     fa[x]=z,fa[y]=x,fa[c[x][r]]=y;
 26     c[y][l]=c[x][r],c[x][r]=y;
 27 }
 28 inline void sply(int x){
 29     stck[tp=1]=x;
 30     for(int i=x;!isrt(i);i=fa[i])  stck[++tp]=fa[i];
 31     while(tp)  pshd(stck[tp--]);
 32     while(!isrt(x)){
 33         if(!isrt(fa[x]))  rtt((c[fa[x]][0]==x)^(c[fa[fa[x]]][0]==fa[x])?x:fa[x]);
 34         rtt(x);
 35     }
 36 }
 37 inline void accs(int x){  for(int i=0;x;sply(x),c[x][1]=i,x=fa[i=x]);}
 38 inline void qdrt(int x){  accs(x),sply(x),rvs[x]^=1;}
 39 inline void lk(int x,int y){  qdrt(x),fa[x]=y,sply(x);}
 40 inline void ct(int x,int y){  qdrt(x),accs(y),sply(y),fa[x]=c[y][0]=0;}
 41 inline void bf(int x,int y){  qdrt(1),accs(x),sply(x),v[x]+=y,dt[x]+=y;}
 42 inline int sch(int x){  sply(x);  return v[x];}
 43 void rds(){
 44     scanf("%s",s);  n=strlen(s);  int tmp=qwq;
 45     for(int i=0;i<n;++i){
 46         tmp=(tmp*131+i)%n;
 47         swap(s[i],s[tmp]);
 48     }
 49 }
 50 /*void ist(int x){
 51     int p=lst,np=lst=++npt;
 52     mx[np]=mx[p]+1;  sz[np]=0;
 53     while((!nxt[p][x])&((!p)^1))  nxt[p][x]=np,p=fth[p];
 54     if(!p)  fth[np]=1;
 55     else{
 56         int q=nxt[p][x];
 57         if(mx[q]==mx[p]+1)  fth[np]=q;
 58         else{
 59             int nq=++npt;  mx[nq]=mx[p]+1;  sz[nq]=sz[q];
 60             memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
 61             fth[nq]=fth[q],fth[q]=fth[np]=nq;
 62             while(nxt[p][x]==q)  nxt[p][x]=nq,p=fth[p];
 63         }
 64     }
 65     while(np)  ++sz[np],np=fth[np];
 66 }*/
 67 void ist(int x){
 68     int p=lst,np=lst=++npt;
 69     mx[np]=mx[p]+1;  v[np]=0;
 70     while((!nxt[p][x])&((!p)^1))  nxt[p][x]=np,p=fth[p];
 71     if(!p)  fth[np]=1,lk(np,1);
 72     else{
 73         int q=nxt[p][x];
 74         if(mx[q]==mx[p]+1)  fth[np]=q,lk(np,q);
 75         else{
 76             int nq=++npt;  mx[nq]=mx[p]+1;  v[nq]=sch(q);
 77             memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
 78             ct(q,fth[q]),lk(nq,fth[q]),lk(q,nq),lk(np,nq);
 79             fth[nq]=fth[q],fth[q]=fth[np]=nq;
 80             while(nxt[p][x]==q)  nxt[p][x]=nq,p=fth[p];
 81         }
 82     }
 83     bf(np,1);
 84     //cout<<sch(5)<<" "<<fth[3]<<endl;
 85 }
 86 int qr(){
 87     int tmp=1;
 88     for(int i=0;i<n;++i)  tmp=nxt[tmp][s[i]-A];
 89     return tmp?sch(tmp):0;
 90 }
 91 int main(){freopen("ddd.in","r",stdin);
 92     cin>>m;  scanf("%s",s);  n=strlen(s);
 93     for(int i=0;i<n;++i)  ist(s[i]-A);
 94     while(m--){
 95         scanf("%s",t);  rds();
 96         if(t[0]==A)  for(int i=0;i<n;++i)  ist(s[i]-A);
 97         else{  int tmp=qr();  qwq^=tmp;  printf("%d\n",tmp);}
 98     }
 99     return 0;
100 }
View Code

 

【BZOJ2555】SubString