首页 > 代码库 > 【BZOJ2555】SubString 后缀自动机+LCT
【BZOJ2555】SubString 后缀自动机+LCT
【BZOJ2555】SubString
Description
懒得写背景了，给你一个字符串init，要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符串s在当前字符串中出现了几次？(作为连续子串) 你必须在线支持这些操作。
Input
第一行一个数Q表示操作个数 第二行一个字符串表示初始字符串init 接下来Q行，每行2个字符串Type,Str
Type是ADD的话表示在后面插入字符串。 Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。 为了体现在线操作，你需要维护一个变量mask，初始值为0 
读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。 询问的时候，对TrueStr询问后输出一行答案Result 然后mask = mask xor Result 插入的时候，将TrueStr插到当前字符串后面即可。
HINT:ADD和QUERY操作的字符串都需要解压
Output
Sample Input
A
QUERY B
ADD BBABBBBAAB
Sample Output
HINT
40 % 的数据字符串最终长度 <= 20000，询问次数<= 1000，询问总长度<= 10000
100 % 的数据字符串最终长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000
题解：将串扔到SAM里，答案就是S的子树中结束节点的个数，由于强制在线只能用LCT维护，加入一个结束节点就将它到根的路径上的所有点权都+1。
discuss说不能用递归来下传标记？不明觉厉，写的非递归。
一开始写的太丑了，然后开始%黄学长的代码，%了一天一夜才搞出来QAQ
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=1200010; int msk,n,m,ans,len; struct LCT { int ch[maxn][2],s[maxn],tag[maxn],fa[maxn],q[maxn]; int isr(int x) {return (ch[fa[x]][0]!=x)&&(ch[fa[x]][1]!=x);} void pushdown(int x) { if(ch[x][0]) s[ch[x][0]]+=tag[x],tag[ch[x][0]]+=tag[x]; if(ch[x][1]) s[ch[x][1]]+=tag[x],tag[ch[x][1]]+=tag[x]; tag[x]=0; } void rotate(int x) { int y=fa[x],z=fa[y],d=(x==ch[y][1]); if(!isr(y)) ch[z][y==ch[z][1]]=x; fa[x]=z,fa[y]=x,ch[y][d]=ch[x][d^1]; if(ch[x][d^1]) fa[ch[x][d^1]]=y; ch[x][d^1]=y; } void updata(int x) { q[0]=0; while(1) { q[++q[0]]=x; if(!isr(x)) x=fa[x]; else break; } for(int i=q[0];i>=1;i--) pushdown(q[i]); } void splay(int x) { updata(x); while(!isr(x)) { int y=fa[x],z=fa[y]; if(!isr(y)) { if((x==ch[y][0])^(y==ch[z][0])) rotate(x); else rotate(y); } rotate(x); } } void access(int x) { int y=0; while(x) splay(x),ch[x][1]=y,y=x,x=fa[x]; } void link(int x,int y) { fa[y]=x,access(x),splay(x),s[x]+=s[y],tag[x]+=s[y]; } void cut(int x) { access(x),splay(x),s[ch[x][0]]-=s[x],tag[ch[x][0]]-=s[x]; fa[ch[x][0]]=0,ch[x][0]=0; } }T; char str[maxn]; struct SAM { int pre[maxn],ch[maxn][26],dep[maxn],last,tot; void add(int x) { int p=last,np=++tot; last=np,dep[np]=dep[p]+1,T.s[np]=1; for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np; if(!p) pre[np]=1,T.link(1,np); else { int q=ch[p][x]; if(dep[q]==dep[p]+1) pre[np]=q,T.link(q,np); else { int nq=++tot; dep[nq]=dep[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq; T.cut(q),T.link(pre[nq],nq),T.link(nq,q),T.link(nq,np); memcpy(ch[nq],ch[q],sizeof(ch[q])); for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq; } } } int query() { int i,p=1; for(i=p=1;i<=len&&p;i++) p=ch[p][str[i-1]-‘A‘]; if(!p) return 0; T.updata(p); return T.s[p]; } }S; void decode() { scanf("%s",str),len=strlen(str); int i,ms=msk; for(i=0;i<len;i++) { ms=(ms*131+i)%len; swap(str[i],str[ms]); } } int main() { scanf("%d",&m); S.last=S.tot=1; int i,j; scanf("%s",str),len=strlen(str); for(i=1;i<=len;i++) S.add(str[i-1]-‘A‘); for(i=1;i<=m;i++) { scanf("%s",str); if(str[0]==‘A‘) { decode(); for(j=1;j<=len;j++) S.add(str[j-1]-‘A‘); } else { decode(),ans=S.query(),msk^=ans; printf("%d\n",ans); } } return 0; }
【BZOJ2555】SubString 后缀自动机+LCT