BSOJ6540题解
整个人场上发麻,有思路但是懒得去推,结果很简单然后就寄了/hanx
注意到一个串的续力值相当于这个串的所有前缀的 Border 的数量。
问题变为计算新加入字符后,所有后缀的上述值。
Insert 一个节点后,考虑上述过程,发现相当于计算每个子串的 Border 数量之和。
自动机上一个节点的 Border 相当于直接跳 fail 指针。这或许能够给我们提示。
考虑到两个完全相同的串一定可以配成一对 Border,无论其是否重叠。考虑两个后缀对答案的贡献。容易发现为 \(lcp(i,j)\)。
于是我们要动态求出 \(\sum_{i=1}^{n}\sum_{j=i+1}^{n}LCP(i,j)\)。
众所周知后缀树的 LCA 就是 LCP。题意变成标记一个点,然后问所有标记点的 LCA 的深度之和。
这和 LNOI2014LCA 没有任何区别。
复杂度 \(O(n\log^2n)\)。
#include
#include
typedef unsigned ui;
const ui M=2e5+5,mod=1e9+7;
ui n,m,cnt,tot(1),lst(1),pos[M],len[M<<1],fail[M<<1],trans[M<<1][26];
ui dfc,h[M<<1],f[M<<1],bl[M<<1],dfn[M<<1],siz[M<<1],son[M<<1],top[M<<1];char s[M];
ui V[M<<3],tag[M<<3],sum[M<<3],*nV=V,*ntag=tag,*nsum=sum;
struct Edge{
ui v,nx;
}e[M<<1];
inline void Add(const ui&u,const ui&v){
e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
}
struct sgt{
ui L,n,G,*V,*tag,*sum;
inline ui init(const ui&u,const ui&m){
n=m;for(G=1;G<=n;G<<=1);L=dfn[u]-1;
for(ui i=1;i<=n;++i)V[i+G]=len[bl[L+i]]-len[f[bl[L+i]]];
for(ui u=G-1;u>=1;--u)V[u]=(V[u<<1]+V[u<<1|1])%mod;
return G<<1;
}
inline void Mdf(ui s,ui t){
ui lz(0),rz(0),sz(1);s-=L;t-=L;
for(s+=G-1,t+=G+1;s^t^1;s>>=1,t>>=1,sz<<=1){
sum[s]=(sum[s]+lz)%mod;sum[t]=(sum[t]+rz)%mod;
if(~s&1)++tag[s^1],sum[s^1]=(sum[s^1]+V[s^1])%mod,lz+=V[s^1];
if(t&1)++tag[t^1],sum[t^1]=(sum[t^1]+V[t^1])%mod,rz+=V[t^1];
}
while(s&&t)sum[s]=(sum[s]+lz)%mod,sum[t]=(sum[t]+rz)%mod,s>>=1,t>>=1;
}
inline ui Qry(ui s,ui t){
ui lz(0),rz(0),sz(1),ans(0);s-=L;t-=L;
for(s+=G-1,t+=G+1;s^t^1;s>>=1,t>>=1,sz<<=1){
ans=(ans+1ull*lz*tag[s]+1ull*rz*tag[t])%mod;
if(~s&1)ans=(ans+sum[s^1])%mod,lz+=V[s^1];
if(t&1)ans=(ans+sum[t^1])%mod,rz+=V[t^1];
}
while(s&&t)ans=(ans+1ull*lz*tag[s]+1ull*rz*tag[t]),s>>=1,t>>=1;
return ans;
}
}SGT[M<<1];
inline void Insert(const ui&c){
ui q,p,nq,np;
p=lst;len[np=lst=++tot]=len[p]+1;
while(p&&!trans[p][c])trans[p][c]=np,p=f[p];
if(!p)f[np]=1;
else{
if(len[q=trans[p][c]]==len[p]+1)f[np]=q;
else{
f[nq=++tot]=f[q];len[nq]=len[p]+1;memcpy(trans[nq],trans[q],104);f[q]=f[np]=nq;
while(p&&trans[p][c]==q)trans[p][c]=nq,p=f[p];
}
}
}
inline void DFS1(const ui&u){
siz[u]=1;
for(ui v,E=h[u];E;E=e[E].nx)if(v=e[E].v){
f[v]=u;DFS1(v);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;
}
}
inline void DFS2(const ui&u,const ui&tp){
top[u]=tp;dfn[u]=++dfc;bl[dfc]=u;
if(son[u])DFS2(son[u],tp);
else{
const ui&v=top[u],&len=dfn[u]-dfn[v]+1;
SGT[v].V=nV;SGT[v].tag=ntag;SGT[v].sum=nsum;
const ui&m=SGT[v].init(v,len);
nV+=m;ntag+=m;nsum+=m;
}
for(ui E=h[u];E;E=e[E].nx)if(e[E].v^son[u])DFS2(e[E].v,e[E].v);
}
inline void Mdf(ui u){
while(u)SGT[top[u]].Mdf(dfn[top[u]],dfn[u]),u=f[top[u]];
}
inline ui Qry(ui u){
ui ans(0);while(u)ans=(ans+SGT[top[u]].Qry(dfn[top[u]],dfn[u]))%mod,u=f[top[u]];return ans;
}
signed main(){
ui sum(0),delta(0);
scanf("%u%s",&n,s+1);
for(ui i=1;i<=n;++i)Insert(s[i]-97),pos[i]=lst;
for(ui u=2;u<=tot;++u)Add(f[u],u);DFS1(1);DFS2(1,1);
for(ui i=1;i<=n;++i){
delta=(mod+delta+Qry(pos[i]))%mod;Mdf(pos[i]);
sum=(sum+delta)%mod;
printf("%u\n",sum);
}
}
实现的时候写的是对线段树的每一条链开一颗 zkw 线段树(