https://www.lydsy.com/JudgeOnline/problem.php?id=4516
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。
SAM傻逼题，然而我把SAM忘光了？
没关系SAM怎么建我还记得，咦SAM怎么统计不同字符串个数来着？
于是我看了一眼BZOJ3998：[TJOI2015]弦论。
我们知道只要遍历后缀自动机就能得到所有不相同的子串，相当于每个节点有价值size=1，如果我们倒序遍历并且累加的话就能求出sum。
当然我们没必要每次都求一遍sum，我们发现我们新加入的节点，其造成的贡献按照我们上面的推论就是tr[np].l-tr[tr[np].fa].l。
（你可以试着画一个简单的后缀自动机感受一下，比如说“1231”，你就会发现实际造成贡献的就是fa~np的每个节点（除np）都由np转移来了+1，这些1需要累加到一起汇总到root，当然同理对于我们因为right集合不同而新开的点也是一样的。）
没了，很水吧。
#include<map> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define fi first #define se second const int N=1e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } map<int,int>::iterator it; struct node{ map<int,int>a; int fa,l; }tr[N<<1]; int n,last,cnt; ll ans; inline void insert(int c){ int p=last,np=++cnt; last=np;tr[np].l=tr[p].l+1; for(;p&&!tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np; if(!p)tr[np].fa=1; else{ int q=tr[p].a[c]; if(tr[p].l+1==tr[q].l)tr[np].fa=q; else{ int nq=++cnt;tr[nq].l=tr[p].l+1; for(it=tr[q].a.begin();it!=tr[q].a.end();it++) tr[nq].a[it->fi]=it->se; tr[nq].fa=tr[q].fa;tr[q].fa=tr[np].fa=nq; for(;tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq; } } ans+=tr[np].l-tr[tr[np].fa].l; } int main(){ n=read(); last=cnt=1; for(int i=1;i<=n;i++){ insert(read());printf("%lld ",ans); } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++