傳送門

Description

給你一個(gè)字符串\(init\)，要求你支持兩個(gè)操作

(1):在當(dāng)前字符串的后面插入一個(gè)字符串

(2):詢問字符串s在當(dāng)前字符串中出現(xiàn)了幾次？(作為連續(xù)子串)

你必須在線支持這些操作。

Solution

一個(gè)字符串出現(xiàn)的次數(shù)\(=\)它所對應(yīng)的\(Right\)集合的大小\(=\)它在\(parent\)樹上的孩子的\(Right\)集合的大小之和

在本題中，我們需要?jiǎng)討B(tài)的維護(hù)\(parnet\)樹的形態(tài)，而這個(gè)是可以通過\(LCT\)實(shí)現(xiàn)的

對于\(val\)值的修改，我們發(fā)現(xiàn)每次加點(diǎn)或刪點(diǎn)都會(huì)影響一條到根路徑上的所有點(diǎn)

我們發(fā)現(xiàn)路徑都是到根的，所以，這里的\(LCT\)就不需要\(makeroot\)操作了

修改，是通過\(lazy\)標(biāo)記實(shí)現(xiàn)噠

Code?

/**************************************************************Problem: 2555User: PaperCloudLanguage: C++Result: AcceptedTime:14492 msMemory:163144 kb ****************************************************************/#include<cstring> #include<cstdio> #include<algorithm> #define get(x) (c[fa[x]][1]==x) #define MS 3000005 #define MX 1200005 char s[MS]; int L,val[MX],lazy[MX]; int fa[MX],c[MX][2]; inline void upd(int x,int v) {if(!x)return;val[x]+=v;lazy[x]+=v; } inline void down(int x) {if(!lazy[x])return;upd(c[x][0],lazy[x]);upd(c[x][1],lazy[x]);lazy[x]=0; } inline bool nrt(int x) {return c[fa[x]][1]==x||c[fa[x]][0]==x; } inline void rotate(int x) {int y=fa[x],z=fa[y],l=get(x),r=l^1;if(nrt(y))c[z][get(y)]=x;fa[x]=z;fa[c[x][r]]=y;c[y][l]=c[x][r];fa[y]=x;c[x][r]=y; } inline void Splay(int x) {static int q[MX],top;q[top=1]=x;register int i;for(i=x;nrt(i);i=fa[i]) q[++top]=fa[i];for(;top;--top) down(q[top]);for(;nrt(x);rotate(x)) if(nrt(fa[x])) rotate(get(x)^get(fa[x])?x:fa[x]); } inline void access(int x) {register int i;for(i=0;x;x=fa[i=x]) Splay(x),c[x][1]=i; } inline void cut(int x) {access(x);Splay(x);upd(c[x][0],-val[x]);fa[c[x][0]]=0;c[x][0]=0; } inline void link(int x,int y) {fa[x]=y;access(y);Splay(y);upd(y,val[x]); } inline void update(int x) {if(!x)return;Splay(x); } int fail[MX],ss[MX][26],step[MX]; int last,cnt; inline void Insert(int x) {int p=last,np=++cnt;step[np]=step[p]+1;val[np]=1;for(;p&&!ss[p][x];p=fail[p]) ss[p][x]=np;if(!p)link(np,1),fail[np]=1;else{int q=ss[p][x];if(step[q]==step[p]+1)link(np,q),fail[np]=q;else{int nq=++cnt;step[nq]=step[p]+1;memcpy(ss[nq],ss[q],sizeof ss[q]);link(nq,fail[q]);cut(q);link(q,nq);link(np,nq);fail[nq]=fail[q];fail[q]=fail[np]=nq;for(;ss[p][x]==q;p=fail[p]) ss[p][x]=nq;}}last=np; } inline int Query(char *s,int L) {register int i,x=1;for(i=0;i<L;++i) x=ss[x][s[i]-'A'];update(x);return val[x]; } int mask=0; int main() {last=cnt=1;int i,q,lastans=0;scanf("%d%s",&q,s+1);L=strlen(s+1);for(i=1;i<=L;++i) Insert(s[i]-'A');char opt[10];while(q--){scanf("%s%s",opt,s);L=strlen(s);int mk=mask;for(i=0;i<L;++i) mk=(mk*131+i)%L,std::swap(s[i],s[mk]);if(opt[0]=='A') for(i=0;i<L;++i) Insert(s[i]-'A');else printf("%d\n",lastans=Query(s,L)),mask^=lastans;}return 0; }

---

Blog來自PaperCloud，未經(jīng)允許，請勿轉(zhuǎn)載，TKS！

轉(zhuǎn)載于:https://www.cnblogs.com/PaperCloud/p/10345681.html

總結(jié)

以上是生活随笔為你收集整理的[bzoj 2555]Substring的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。