Description
给定一个字符串 init，要求支持两个操作：
-
在当前字符串的后面插入一个字符串。
-
询问字符串 $s$ 在当前字符串中出现了几次。(作为连续子串)
强制在线。
Solution
由于需要求字符串的出现次数，所以使用SAM
一个模式串在文本串中的出现次数是其对应点的子树endpos并的大小（parent树上对应点的子树大小），此处为了防止重复应该只计算为前缀的节点（即非复制而来的点）
所以对于所有非复制而来的点，权值为$1$
由于在构建SAM的过程中有的点会更改后缀链接，即有断边和加边的操作，所以应该用LCT维护
在LCT中维护虚边子树和与子树和，答案为
$$lsiz[p]+siz[ch[p][1]]+v[p]$$
$lsiz$为虚边子树和，$v$为权值
数据：链接：https://pan.baidu.com/s/1C6V4R4LlEG3UfHvciSaVkg 提取码：6kgh
#include<iostream> #include<cstring> #include<cstdio> using namespace std; namespace LCT { int tree[8000005][2],tag[8000005],tag2[8000005],fa[8000005],st[8000005],top,rev[8000005],v[8000005]; void pushdown(int x) { if(rev[x]) { if(tree[x][0]) { rev[tree[x][0]]^=1; swap(tree[tree[x][0]][0],tree[tree[x][0]][1]); } if(tree[x][1]) { rev[tree[x][1]]^=1; swap(tree[tree[x][1]][0],tree[tree[x][1]][1]); } rev[x]=0; } } void pushup(int x) { tag[x]=tag[tree[x][0]]+tag[tree[x][1]]+tag2[x]+v[x]; } bool nroot(int x) { return tree[fa[x]][0]==x||tree[fa[x]][1]==x; } int getson(int x) { return tree[fa[x]][1]==x; } void rotate(int x) { int y=fa[x],z=fa[y],b=getson(x),c=getson(y),a=tree[x][!b]; if(nroot(y)) { tree[z][c]=x; } fa[x]=z; tree[x][!b]=y; fa[y]=x; tree[y][b]=a; if(a) { fa[a]=y; } pushup(y); pushup(x); } void splay(int x) { int top=0; st[++top]=x; for(int i=x;nroot(i);i=fa[i]) { st[++top]=fa[i]; } while(top) { pushdown(st[top--]); } while(nroot(x)) { int y=fa[x]; if(nroot(y)) { getson(x)^getson(y)?rotate(x):rotate(y); } rotate(x); } } void access(int x) { for(int y=0;x;x=fa[y=x]) { splay(x); tag2[x]+=tag[tree[x][1]]-tag[y]; tree[x][1]=y; pushup(x); } } void makeroot(int x) { access(x); splay(x); rev[x]^=1; swap(tree[x][0],tree[x][1]); } void split(int x,int y) { makeroot(x); access(y); splay(y); } void link(int x,int y) { split(x,y); fa[x]=y; tag2[y]+=tag[x]; pushup(y); } void cut(int x,int y) { split(x,y); tree[y][0]=fa[x]=0; pushup(y); } } int q,las=1,tot=1,ans,mask; char str[8000005]; struct SAM { int ch[2],fa,len; }sam[8000005]; inline int read() { int w=0,f=1; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return w*f; } void decodeWithMask(int mask) { scanf("%s",str); int m=strlen(str); for(int j=0;j<m;j++) { mask=(mask*131+j)%m; swap(str[mask],str[j]); } } void insert(int c) { int p=las,np=las=++tot; sam[np].len=sam[p].len+1; for(;p&&!sam[p].ch[c];p=sam[p].fa) { sam[p].ch[c]=np; } if(!p) { sam[np].fa=1; } else { int q=sam[p].ch[c]; if(sam[q].len==sam[p].len+1) { sam[np].fa=q; } else { int nq=++tot; sam[nq]=sam[q]; LCT::link(nq,sam[nq].fa); sam[nq].len=sam[p].len+1; LCT::cut(q,sam[q].fa); sam[q].fa=sam[np].fa=nq; LCT::link(q,nq); for(;p&&sam[p].ch[c]==q;p=sam[p].fa) { sam[p].ch[c]=nq; } } } LCT::tag[np]=LCT::v[np]=1; LCT::link(np,sam[np].fa); } int main() { q=read(); scanf("%s",str); for(int i=0;str[i];i++) { insert(str[i]-'A'); } for(int i=1;i<=q;i++) { char opt[10]; scanf("%s",opt); decodeWithMask(mask); if(opt[0]=='A') { for(int j=0;str[j];j++) { insert(str[j]-'A'); } } else { int p=1; for(int j=0;str[j]&&p;j++) { p=sam[p].ch[str[j]-'A']; } if(p) { LCT::makeroot(1); LCT::access(p); LCT::splay(p); ans=LCT::tag2[p]+LCT::tag[LCT::tree[p][1]]+LCT::v[p]; } else { ans=0; } mask^=ans; printf("%d ",ans); } } return 0; }