【BZOJ4545】DQS的trie

Description

DQS的自家陽臺上種著一棵顆粒飽滿、顏色純正的trie。 DQS的trie非常的奇特，它初始有n0個節點，n0-1條邊，每條邊上有一個字符。并且，它擁有極強的生長力：某個i時刻，某個節點就會新生長出一顆子樹，它擁有si個節點且節點之間的邊上有一個字符，并且新生長出來的子樹也是一個樹結構。然而因為是新長出來的，根據生活常識可知si必定不會大于i時刻之前的樹的大小。 DQS定義trie的子串為從根節點（1號節點）往下走到所有節點所構成的字符串的所有的后綴。DQS身為一個單身doge，常常取出其中一個子串送給妹子，然而他并不希望送給妹子兩個相同的子串，所以他非常關心當前trie的本質不同的子串數目。 DQS有時還會去商店購買子串，若他在商店看上某個子串，他希望得知這個子串是否在自家陽臺的trie上已經出現，若出現則出現了多少次。如果出現了，他就可以直接回家取trie上的子串辣！ 然而DQS身為一個蒟蒻，看著自家陽臺的trie樹一天天在長大，他被如此眾多的節點弄得眼花繚亂，于是他找到了IOI2016Au的你。他會告訴你自家trie樹的成長歷程，他希望你能夠對于每一次詢問都做出正確回復。

Input

第一行輸入一個整數id，代表測試點編號。 接下來一行輸入一個整數n0，表示初始樹的大小。 接下來n0-1行，每行兩個整數u,v和一個字符c，表示u號節點和v號節點之間有一條邊，邊上的字母為c。 接下來輸入m表示有m組操作。 對于每一組，第一行輸入一個整數opt。 若opt=1，則是一組詢問，詢問當前trie的本質不同的子串數目是多少。 若opt=2，則后面跟兩個整數rt,si，表示以點rt為根向下長出一個子樹，大小為si。 接下來si-1行，每行兩個整數u,v和一個字符c，表示u號節點和v號節點之間有一條邊，邊上的字母為c。若長出子樹之前當前樹的大小是n，則這si-1點的編號分別為n+1,n+2…n+si-1。 若opt=3，則是一組詢問，后面輸入一個字符串S，詢問字符串S在當前trie中的出現次數。?

Output

對于每個opt=1或3，輸出一行表示答案。

Sample Input

1
4
1 2 a
1 3 b
2 4 b
6
1
2 2 4
2 5 b
2 6 c
5 7 b
1
3 ab
2 6 3
6 8 a
6 9 b
1

Sample Output

3
7
2
11
【數據范圍及提示】
第一個詢問，本質不同的子串是 a,b,ab。
第二個詢問，本質不同的子串是 a,b,c,ab,ac,bb,abb。
第三個詢問，ab出現次數是 2。
第四個詢問，本質不同的子串是 a,b,c,ab,ac,ca,cb,bb,abb,aca,acb。
opt=1或3時對原樹不做修改，只是詢問。
每次opt=2，會增加si-1個節點，因為有一個節點是原樹上作為新樹的根出現的。
數據中，對于鏈的部分分，滿足端點為根節點，每次新建子樹都從尾部插入。
對于全部數據，保證從始至終每條邊上的字符均為小寫字母’a’或’b’或’c’。
n是最終樹的大小,N<=100000,M<=100000,Si<=當前樹的大小

題解：本題就是3998和2555的結合體，沒做過的直接去做那兩題吧。

對于第一問，我們可以動態維護所有點的mx[i]-mx[pre]之和，對于第二問，用LCT維護pre樹，并將 插入一棵子樹，求一個點的子樹大小 變成?修改一條鏈上的權值，查詢一個點的值?即可。

?

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=400010; typedef long long ll; int n,m,tot,len,cnt; int to[maxn],next[maxn],val[maxn],head[maxn],pos[maxn]; ll ans; char str[maxn]; namespace LCT {struct node{int ch[2],fa;ll tag,val;}s[maxn];int st[maxn],top;inline bool isr(int x) {return (x!=s[s[x].fa].ch[0])&&(x!=s[s[x].fa].ch[1]);}inline void pushdown(int x){if(s[x].tag){if(s[x].ch[0]) s[s[x].ch[0]].val+=s[x].tag,s[s[x].ch[0]].tag+=s[x].tag;if(s[x].ch[1]) s[s[x].ch[1]].val+=s[x].tag,s[s[x].ch[1]].tag+=s[x].tag;s[x].tag=0;}}inline void rotate(int x){int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);if(!isr(y)) s[z].ch[y==s[z].ch[1]]=x;s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;s[x].ch[d^1]=y;}inline void updata(int x){int y=x;st[top=1]=x;while(!isr(y)) y=s[y].fa,st[++top]=y;while(top) pushdown(st[top--]);}inline void splay(int x){updata(x);while(!isr(x)){int y=s[x].fa,z=s[y].fa;if(!isr(y)){if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x);else rotate(y);}rotate(x);}}inline void access(int x){for(int y=0;x;splay(x),s[x].ch[1]=y,y=x,x=s[x].fa);}inline void link(int x,int y){access(x),splay(x),s[y].fa=x,s[x].val+=s[y].val,s[x].tag+=s[y].val;}inline void cut(int x){access(x),splay(x),s[s[x].ch[0]].val-=s[x].val,s[s[x].ch[0]].tag-=s[x].val;s[s[x].ch[0]].fa=0,s[x].ch[0]=0;} } namespace SAM {int ch[maxn][26],pre[maxn],mx[maxn];char str[maxn];inline int extend(int p,int x){int np=++tot;mx[np]=mx[p]+1,LCT::s[np].val=1;for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np;if(!p) pre[np]=1,ans+=mx[np],LCT::link(1,np);else{int q=ch[p][x];if(mx[q]==mx[p]+1) pre[np]=q,ans+=mx[np]-mx[q],LCT::link(q,np);else{int nq=++tot; mx[nq]=mx[p]+1;ans-=mx[q]-mx[pre[q]];LCT::cut(q);pre[nq]=pre[q],pre[np]=pre[q]=nq;ans+=mx[nq]-mx[pre[nq]]+mx[np]-mx[pre[np]]+mx[q]-mx[pre[q]];LCT::link(pre[nq],nq),LCT::link(pre[q],q),LCT::link(pre[np],np);memcpy(ch[nq],ch[q],sizeof(ch[q]));for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;}}return np;}inline void query(){scanf("%s",str),len=strlen(str);int i,p=1;for(i=0;i<len&&p;i++) p=ch[p][str[i]-'a'];if(!p) puts("0");else{LCT::updata(p);printf("%lld\n",LCT::s[p].val);}} } inline int rd() {int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();return ret*f; } void dfs(int x,int fa) {for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) pos[to[i]]=SAM::extend(pos[x],val[i]),dfs(to[i],x);head[x]=-1; } inline void add(int a,int b,int c) {to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++; } int main() {rd(),n=rd();int i,a,b,c,d,op;tot=1,pos[1]=1;memset(head,-1,sizeof(head));for(i=1;i<n;i++) a=rd(),b=rd(),scanf("%s",str),add(a,b,str[0]-'a'),add(b,a,str[0]-'a');dfs(1,0);m=rd();for(i=1;i<=m;i++){op=rd();if(op==1) printf("%lld\n",ans);if(op==2){c=rd(),d=rd();while(--d) a=rd(),b=rd(),scanf("%s",str),add(a,b,str[0]-'a'),add(b,a,str[0]-'a');dfs(c,0);}if(op==3) SAM::query();}return 0; }//1 4 1 2 a 1 3 b 2 4 b 6 1 2 2 4 2 5 b 2 6 c 5 7 b 1 3 ab 2 6 3 6 8 a 6 9 b 1

?

轉載于:https://www.cnblogs.com/CQzhangyu/p/7859563.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【BZOJ4545】DQS的trie 后缀自动机+LCT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。