正題

題目鏈接:http://www.51nod.com/Challenge/Problem.html#problemId=1600

---

題目大意

給出一個字符串$s$，每次在最后插入一個字符后求它的所有分別子串構出的$fail$樹的深度和。

$1\le Q\le 10^5$

---

解題思路

考慮兩個相等的子串長度為$len$，那么以后面那個子串末尾結尾的$fail$有$len$種左端點的情況是指向前面那個子串的。

新插入后所有串的后綴都是新的子串，考慮如何統計這些串的答案，首先不考慮最后一個位置那么深度和就是前面那次新加的深度和。現在只需要計算新插入那個字符在這$n$個串中的貢獻，我們可以找出所有和這些串的所有后綴相同的子串都會產生貢獻，這個可以用$SAM$統計。

所以可以考慮先把完整的串的$SAM$建出來再考慮做法，每次插入一個字符串的時候先查詢它在$parents$樹上到根的路徑的邊權乘上邊的長度和，然后再向這條路徑上每條邊的權值加一。

注意到要路徑加權求和，所以要加一個樹剖就可以了

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=4e5+10,P=1e9+7; struct node{int to,next; }a[N]; int n,cnt,last,tot,dfc,p[N],ls[N]; int siz[N],son[N],top[N],dfn[N],rfn[N]; int fa[N],ch[N][26];ll len[N]; char s[N];bool v[N]; struct SegTree{ll w[N<<2],lazy[N<<2];void Downdata(int x,int L,int R){if(!lazy[x])return;int mid=(L+R)>>1;w[x*2]=(w[x*2]+lazy[x]*(len[dfn[mid]]-len[dfn[L-1]]))%P;w[x*2+1]=(w[x*2+1]+lazy[x]*(len[dfn[R]]-len[dfn[mid]]))%P;lazy[x*2]+=lazy[x];lazy[x*2+1]+=lazy[x];lazy[x]=0;return;}void Change(int x,int L,int R,int l,int r){if(L==l&&R==r){(w[x]+=len[dfn[R]]-len[dfn[L-1]])%=P;lazy[x]++;return;}int mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)Change(x*2,L,mid,l,r);else if(l>mid) Change(x*2+1,mid+1,R,l,r);else Change(x*2,L,mid,l,mid),Change(x*2+1,mid+1,R,mid+1,r);w[x]=(w[x*2]+w[x*2+1]);return;}ll Ask(int x,int L,int R,int l,int r){if(L==l&&R==r)return w[x];int mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return (Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r))%P;} }T; void Insert(int c){int p=last,np=last=++cnt;len[np]=len[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{int q=ch[p][c];if(len[q]==len[p]+1)fa[np]=q;else{int nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}v[np]=1;return; } void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){siz[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dfs(y);siz[x]+=siz[y];len[y]=len[y]-len[x];if(siz[y]>siz[son[x]])son[x]=y;}return; } void dfs2(int x){dfn[++dfc]=x;rfn[x]=dfc;if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==son[x])continue;top[y]=y;dfs2(y);}return; } void print(int x) {if(x>9)print(x/10);putchar(x%10+48);return;} signed main() {freopen("string.in","r",stdin);freopen("string.out","w",stdout);scanf("%d",&n);scanf("%s",s+1);last=cnt=1;for(int i=1;i<=n;i++)Insert(s[i]-'a'),p[i]=last;for(int i=2;i<=cnt;i++)addl(fa[i],i);top[1]=1;dfs(1);dfs2(1);ll k=0,ans=0;for(int i=1;i<=cnt;i++)len[dfn[i]]=(len[dfn[i]]+len[dfn[i-1]])%P;for(int i=1;i<=n;i++){int x=p[i];while(x){k=(k+T.Ask(1,1,cnt,rfn[top[x]],rfn[x]))%P;x=fa[top[x]];}ans=(ans+k)%P;x=p[i];while(x){T.Change(1,1,cnt,rfn[top[x]],rfn[x]);x=fa[top[x]];}print((ans+P)%P);putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的51nod1600-Simple KMP【SAM,树链剖分】的全部內容，希望文章能夠幫你解決所遇到的問題。

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