我们知道统计本质不同的子串个数是$SAM$的经典应用之一
这道题要求在线统计，且字符集大小为$1e9$，怎么办？
先解决字符集的问题，我们只需要将 tr[][] 数组改成$map$即可
至于统计本质不同的子串数，那就是$\sum max(x)-min(x)+1$
因为$min(x)=max(parent(x))+1$，所以也就是求 $\sum max(x)-max(parent(x))$
在线统计时，我们每新建一个节点$np$，就统计它的答案即可
在做题的时候，我一直有一个疑问，那就是为什么不统计新建的nq节点的答案呢？
新建节点前：
(1) $ans(q)=max(q)-max(parent(q))$
新建$nq$节点后：parent(q)$变成了nq，parent(nq)$变成了parent(q)
(2) $ans(q)=max(q)-max(nq)$
(3) $ans(nq)=max(nq)-max(parent(q))$
$(2)(3)$两式相加，我们发现新建节点后的$ans(q)+ans(nq)$的答案与新建节点前$ans(q)$是相等的
这就完美的解释了为什么不统计$nq$节点的答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<bits/stdc++.h> #define MAXN 200010 #define FILE "read" using namespace std; typedef long long ll; int n,cnt(1),now(1),mx[MAXN],par[MAXN]; map<int,int> tr[MAXN]; ll ans; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void extend(int x){ int np=++cnt,p=now; mx[np]=mx[p]+1; now=np; while(p&&!tr[p][x]) tr[p][x]=np,p=par[p]; if(!p) par[np]=1; else{ int q=tr[p][x]; if(mx[q]==mx[p]+1) par[np]=q; else{ int nq=++cnt; mx[nq]=mx[p]+1; tr[nq]=tr[q]; par[nq]=par[q]; par[q]=par[np]=nq; while(tr[p][x]==q&&p) tr[p][x]=nq,p=par[p]; } } ans+=mx[np]-mx[par[np]]; printf("%lld\n",ans); } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); for(int i=1;i<=n;++i){ int x=read(); extend(x); } return 0; }
|