题目大意

给定一个长度为 n 的字符串（只包含数字），我们定义Fi表示在第 i 个字符后面断开后，两个字符串的本质不同的子串个数。请快速求出F。 1≤n≤5×105

---

题目分析

这道题正着很难做（xdl好像在考场上做到了 O(nlog2n) ）。 我们考虑正难则反：本来我们是对每个 i 求有多少个本质不同的子串至少有一次出现不包括位置i，现在我们转化为求每次出现都包括 i ，然后使用总的本质不同子串个数减去它。 先考虑一个子串S，令它最小出现位置为 minp ，最大出现位置为 maxp ，长度为 len ，那么我们分情况讨论：

minp≤maxp−len ，如果这样的话，这个串至少有两个出现位置是不重叠的，那么它对答案是没有任何贡献的。 minp>maxp−len ，这时候这个子串就会区间 [maxp−len,minp) 的 F 做出1的贡献

但是子串的个数是 O(n2) 的，我们总不能依次枚举吧。像这种统计子串信息的题目，我们应该想到后缀自动机。但是后缀自动机里面，一个节点可能代表多个子串，那么情况就会变得复杂一点。 令节点 x 的最小出现位置为minp，最大出现位置为 maxp ，最小长度为 minl ，最大长度为 maxl 。前两个值可以使用类似统计 size 的方法按照拓扑序统计出来，第三个值就是 parent(x) 的 len 加 1 ，第四个值就是len(x)。 首先如果 minp≤maxp−maxl ，那么这个节点对答案是没有贡献的。 否则这个节点对 F 的贡献相当于区间加上一个首项1共差 1 的等差数列，然后再区间加同一个值。对于区间(maxp−maxl,maxp−minl+1]的 F ，贡献就分别是1,2,3,4...（每次增加一个能够覆盖的子串）。对于区间 (maxp−minl+1,minp) 的 F ，贡献则是r−l+1（该节点所有子串都能覆盖这里）。 这里我们要支持加入一个等差数列，还有区间加一个值。这个不带 log 怎么做啊？ 然而这里我们不一定要在线。考虑对 F 数组差分得到fi=Fi−Fi−1。那么区间加工差为 1 的等差数列，相当于给一个区间加上1，这个是可以使用前缀和统计的。后面那部分加同样的数的区间，我们之间单点修改它的结束位置与上一位的差（ r−l+1 ）。 然后最后再次做一遍前缀和就是答案了。 时间复杂度 O(n) ，如果还有疑惑可以参看一下代码实现。 好久没有打后缀自动机，都快要忘了，一个下午复习了一下，总算记起来了。

---

代码实现

#include <algorithm> #include <iostream> #include <cstdio> #include <cctype> #include <queue> using namespace std; const int MOD=1000000007; const int P=100013; const int N=500050; const int S=N<<1; const int C=10; int add[N],f[N],cnt[N],a[S]; int n,suf,tot,sum,ans; char s[N]; struct node { int mxp,mip,mxl,mil,len,prt; int next[C]; }sam[S]; int insert(int last,int c,int pos) { int np=++tot,p=last,q; for (sam[np].mip=sam[np].mxp=pos,sam[np].len=sam[p].len+1;p&&!sam[p].next[c];p=sam[p].prt) sam[p].next[c]=np; if (!p) sam[np].prt=1; else if (sam[q=sam[p].next[c]].len==sam[p].len+1) sam[np].prt=q; else { int nq=++tot; sam[nq]=sam[q],sam[nq].len=sam[p].len+1; sam[nq].mip=n,sam[nq].mxp=-1; sam[q].prt=sam[np].prt=nq; for (;p&&sam[p].next[c]==q;p=sam[p].prt) sam[p].next[c]=nq; } return np; } void sorts() { for (int i=1;i<=tot;i++) cnt[sam[i].len]++; for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; for (int i=1;i<=tot;i++) a[cnt[sam[i].len]--]=i; } int main() { freopen("knight.in","r",stdin),freopen("knight.out","w",stdout); scanf("%d",&n),scanf("%s",s),tot=suf=1; for (int i=0;i<n;i++) suf=insert(suf,s[i]-'0',i); for (int i=tot;i>1;i--) (sum+=(sam[i].len-sam[sam[i].prt].len))%=MOD; sorts(); for (int i=tot,x;i>1;i--) { sam[x=sam[a[i]].prt].mip=min(sam[x].mip,sam[a[i]].mip),sam[x].mxp=max(sam[x].mxp,sam[a[i]].mxp); sam[a[i]].mxl=sam[a[i]].len,sam[a[i]].mil=sam[x].len+1; } for (int i=2;i<=tot;i++) { int l=sam[i].mil,r=sam[i].mxl; l=max(l,sam[i].mxp-sam[i].mip+1); if (l>r) continue; add[sam[i].mxp-r+1]++; add[sam[i].mxp-l+2]--; (((f[sam[i].mip]-=(r-l+1))%=MOD)+=MOD)%=MOD; } for (int k=0,i=0;i<n;i++) (k+=add[i])%=MOD,(f[i]+=k)%=MOD; for (int i=1;i<n;i++) (f[i]+=f[i-1])%=MOD; for (int i=0;i<n;i++) f[i]=(sum-f[i]+MOD)%MOD; for (int i=n-2,pw=1;i>=0;i--,pw=1ll*pw*P%MOD) (ans+=1ll*f[i]*pw%MOD)%=MOD; printf("%d\n",ans); fclose(stdin),fclose(stdout); }