[Str记录]P5115 Check,Check,Check one two!
command_block
2021-06-26 15:46:57
**题意** ： 给定长为 $n$ 的字符串 $S$。
记 ${\rm lcp}(i,j)$ 为 $S[i:]$ 与 $S[j:]$ 的最长公共前缀长度。
记 ${\rm lcs}(i,j)$ 为 $S[:i]$ 与 $S[:j]$ 的最长公共后缀长度。
给出常数 $k_1,k_2$ ，求下列式子的值。
$$\sum_{1\leq i<j \leq n}{\rm lcp}(i,j){\rm lcs}(i,j)[{\rm lcp}(i,j)\leq k_1][{\rm lcs}(i,j) \leq k_2]$$
答案对 $2^{64}$ 取模。
$n\leq10^5$ ，字符集为小写英文字母，时限$\texttt{2s}$。
------------
好题。
对于 $(i,j)$ ，显然 $S[i-{\rm lcs}(i,j)+1,i+{\rm lcp}(i,j)-1]$ 和 $S[j-{\rm lcs}(i,j)+1,j+{\rm lcp}(i,j)-1]$ 是完全相同的，且向两侧延伸的长度是极长的。
枚举所有这样的 $(i,j)$ 对应的极长串对，计算贡献。
对于一个子串 $T$ 的两次出现，如果这两次出现都是**极长**的（即向两侧扩展后不相同），则可以贡献。
具体地，贡献值为 ：
$$\sum\limits_{k=1}^{|T|}[k\leq k_2]\big[|T|-k+1\leq k_1\big]k\big(|T|-k+1\big)$$
首先枚举中心（即 $(i,j)$）在串中的位置，然后将两侧可以延伸的距离乘起来求和。
上式中唯一的变量为 $|T|$ ，得知 $k_1,k_2$ 后可以 $O(n)$ 预处理。（具体方法见代码）
对 $S$ 建立 $\rm SAM$ 。
对于每个 $\rm SAM$ 节点，显然只有最长串可能产生极长串对。（其他串产生的串对都能扩展为最长串）
观察 $\text{parent-Tree}$ 上极长串对的结构。两个 $\rm edp$ 在它们的 $\rm lca$ 处才有可能产生极长串对，在更浅的祖先处则不再是极长的。
这提示我们在树上合并。
观察两个在 $\rm lca$ 处相遇的 $\rm edp$ ，它们的前面已经确定不能扩展，但后面仍然有可能扩展。
于是暴力记下后方下一个字符的情况。记 $f_u[c]$ 表示 $u$ 子树中的 $\rm edp$ 下一个是 $c$ 的个数。
当两组 $\rm edp$ 合并时，利用 $f$ 容易算出产生的极长串对。
复杂度 $O(n\Sigma)$。 若字符集较大，使用启发式合并可以做到 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pb push_back
#define ull unsigned long long
#define MaxN 100500
using namespace std;
struct Node{int t[26],len,f,ed;}a[MaxN<<1];
int tn,las;
void add(int c)
{
int np=++tn,p=las;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;
}
}
}
char s[MaxN];
int n,k1,k2;ull f[MaxN];
ull calc(int l,int r){return l<=r ? 1ull*(l+r)*(r-l+1)/2 : 0;}
void Init()
{
f[1]=1;
for (int t=1;t<n;t++){
int tl=max(1,t+2-k1),tr=min(t+1,k2);
f[t+1]=f[t]+calc(tl,tr);
int k=t-k1+1;
if (1<=k&&k<=tr)f[t+1]-=1llu*k1*(t-k1+1);
}
}
vector<int> g[MaxN<<1];
ull ans,o[MaxN<<1][27];
void dfs(int u)
{
if (a[u].ed){
if (a[u].ed!=n)o[u][s[a[u].ed+1]-'a']++;
o[u][26]++;
}
for (int i=0,v;i<g[u].size();i++){
dfs(v=g[u][i]);
ull buf=o[u][26]*o[v][26];
for (int i=0;i<26;i++)
buf-=o[u][i]*o[v][i];
ans+=buf*f[a[u].len];
for (int i=0;i<=26;i++)o[u][i]+=o[v][i];
}
}
int main()
{
scanf("%s%d%d",s+1,&k1,&k2);
n=strlen(s+1);tn=las=1;
Init();
for (int i=1;i<=n;i++)add(s[i]-'a');
for (int i=1,p=1;i<=n;i++)
a[p=a[p].t[s[i]-'a']].ed=i;
for (int i=2;i<=tn;i++)g[a[i].f].pb(i);
dfs(1);
printf("%lld\n",ans);
return 0;
}
```