51Node-1600 Simple KMP (后缀自动机+树剖线段树/LCT)
题面给人一种非常复杂的感觉
我们考虑每次加入一个字符，产生的每一个新的后缀的贡献
对于后缀\(S_{x,i}\)我们可以从\(i-1\)继承过来得到\(S_{x,i-1}\)的答案，只用考虑\(i\)的贡献
任意一个\(S_{j,i}(j\leq i)\)在\(x(x<i)\)位置的出现就是\(S_{x,i}\)这个子串的\(fail\)树深度+1
任意一个\(S_{j,i}\)所对应的状态就是\(S_{1,i}\)对应状态\(p\)在\(parent/link\)树上的祖先
可以看到这个出现就是$\sum_{j\in link[..link[p]],k\in endpos_j,k<i} len[j]-len[link[j]] $
可以对于 \(parent/link\) 树用树剖+线段树/LCT维护
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
int rd(){
int s=0;
int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=2e5+10,P=1e9+7;
int n;
char s[N];
int trans[N][26],link[N],len[N],lst,stcnt;
void Init(){
link[0]=-1,len[0]=0;
rep(i,0,stcnt) rep(j,0,25) trans[i][j]=0;
lst=stcnt=0;
}
int pos[N];
void Extend(int c) {
int cur=++stcnt,p=lst;
pos[len[cur]=len[p]+1]=cur;
while(~p && !trans[p][c]) trans[p][c]=cur,p=link[p];
if(p==-1) link[cur]=0;
else {
int q=trans[p][c];
if(len[q]==len[p]+1) link[cur]=q;
else {
int clone=++stcnt;
memcpy(trans[clone],trans[q],104);
len[clone]=len[p]+1,link[clone]=link[q];
while(~p && trans[p][c]==q) trans[p][c]=clone,p=link[p];
link[cur]=link[q]=clone;
}
}
lst=cur;
}
struct Edge{
int to,nxt;
}e[N];
int head[N],ecnt;
void AddEdge(int u,int v){
e[++ecnt]=(Edge){v,head[u]};
head[u]=ecnt;
}
#define erep(u,i) for(reg int i=head[u];i;i=e[i].nxt)
int top[N],sz[N],son[N],L[N],R[N],dfn,id[N];
void dfs1(int u) {
sz[u]=1;
erep(u,i) {
int v=e[i].to;
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int t) {
id[L[u]=++dfn]=u,top[u]=t;
if(son[u]) dfs2(son[u],t);
erep(u,i) {
int v=e[i].to;
if(v==son[u]) continue;
dfs2(v,v);
}
R[u]=dfn;
} // 树剖
struct I_Hate_It{
ll w[N<<2];
void Build(int p,int l,int r) {
if(l==r) {
w[p]=id[l]?(len[id[l]]-len[link[id[l]]]):0;
return;
}
int mid=(l+r)>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
w[p]=w[p<<1]+w[p<<1|1];
} // 预处理权值和
ll s[N<<2],t[N<<2];
void Down(int p) {
if(!t[p]) return;
t[p<<1]+=t[p],t[p<<1|1]+=t[p];
s[p<<1]+=t[p]*w[p<<1],s[p<<1|1]+=t[p]*w[p<<1|1];
t[p]=0;
}
void Up(int p) { s[p]=s[p<<1]+s[p<<1|1]; }
void Upd(int p,int l,int r,int ql,int qr) {
if(ql==l&&qr==r) {
t[p]++,s[p]+=w[p];
return;
}
int mid=(l+r)>>1;
Down(p);
if(qr<=mid) Upd(p<<1,l,mid,ql,qr);
else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr);
else Upd(p<<1,l,mid,ql,mid),Upd(p<<1|1,mid+1,r,mid+1,qr);
Up(p);
} // 累和时还要*权值
ll Que(int p,int l,int r,int ql,int qr) {
if(ql==l&&qr==r) return s[p];
Down(p);
int mid=(l+r)>>1;
if(qr<=mid) return Que(p<<1,l,mid,ql,qr);
else if(ql>mid) return Que(p<<1|1,mid+1,r,ql,qr);
else return Que(p<<1,l,mid,ql,mid)+Que(p<<1|1,mid+1,r,mid+1,qr);
}
}Tree;
void Upd(int x) {
while(~x) {
Tree.Upd(1,1,dfn,L[top[x]],L[x]);
x=link[top[x]];
}
}
ll Que(int x) {
ll res=0;
while(~x) {
res+=Tree.Que(1,1,dfn,L[top[x]],L[x]);
x=link[top[x]];
}
return res;
}
ll ans,res;
int main(){
n=rd();
scanf("%s",s+1);
Init();
rep(i,1,n) Extend(s[i]-'a');
rep(i,1,stcnt) AddEdge(link[i],i);
dfs1(0);
dfs2(0,0);
Tree.Build(1,1,dfn);
int p=0;
rep(i,1,n) {
p=trans[p][s[i]-'a'];
res+=Que(p); // 查询路径和
res%=P;
Upd(pos[i]); // 将<i的加入endpos，路径更新
ans+=res,ans%=P;
printf("%lld\n",ans);
}
}