CF1276F Asterisk Substrings【endpos后缀的本质不同串个数(dfs序并)】

题目分析：

$s,s*,*t$s,s∗,∗t 都很好求，问题主要在与 $s\!*\!t$s∗t
考虑枚举本质不同的 $s$s，需要借助后缀自动机。
发现对于 $endpos$endpos 集合相同的 $s$s，可选的 $t$t 的集合都是一样的，即对于后缀自动机上的节点 $u$u，它对答案的贡献是$(len[u]-len[fa[u]])*$(len[u]−len[fa[u]])∗ $(\cup_{p\in endpos_u}~s[p+2,n]$(∪p∈endposu​​ s[p+2,n] 这些后缀中的本质不同后缀个数$)$)。

而求多个后缀的并的不同的后缀个数，用后缀数组或后缀自动机都可以解决。
后缀数组就是将对应的后缀按照 $rank$rank 排序后每个后缀的长度减去相邻两个后缀的 $\texttt{LCP}$LCP。
后缀自动机就是建出反串的后缀自动机，把对应的后缀在自动机上的对应节点按照 $dfs$dfs 序排序后每个后缀的 $len$len 减去相邻两个后缀的 $\texttt{LCA}$LCA 的 $len$len。

这两种做法都可以在$fail$fail树上转移时用 线段树合并 或 $set$set 启发式合并维护。线段树合并需要记录最左和最右的点。

Code（后缀自动机+线段树合并）：

#include<bits/stdc++.h>
#define maxn 200005
#define maxp maxn*17
#define LL long long
using namespace std;
const int Log = 18;
int n,dfn[maxn],tim,st[Log+1][maxn*2],lg[maxn*2];
int rt[maxn*2],lc[maxp],rc[maxp],pl[maxp],pr[maxp],tot;
LL ans,sum[maxp];
int DLCA(int x,int y){
	if(!x||!y) return 0;
	int k=lg[y-x+1];
	return min(st[k][x],st[k][y-(1<<k)+1]);
}
void upd(int i){
	sum[i]=sum[lc[i]]+sum[rc[i]]-DLCA(pr[lc[i]],pl[rc[i]]);
	pl[i]=pl[lc[i]?lc[i]:rc[i]];
	pr[i]=pr[rc[i]?rc[i]:lc[i]];
}
void ins(int &i,int l,int r,int x){
	i=++tot;
	if(l==r) return (void)(pl[i]=pr[i]=x,sum[i]=st[0][x]);
	int mid=(l+r)>>1;
	x<=mid?ins(lc[i],l,mid,x):ins(rc[i],mid+1,r,x);
	upd(i);
}
void merge(int &i,int x,int y){
	if(!x||!y) return void(i=x+y);
	if(lc[x]||rc[x]) i=x,merge(lc[i],lc[x],lc[y]),merge(rc[i],rc[x],rc[y]),upd(i);
	else assert(0);//when reach leaves. this problem no else.
}
struct SAM{
	int fa[maxn],ch[maxn][26],len[maxn],pos[maxn],last,sz;
	vector<int>G[maxn];
	SAM(){fa[0]=-1;}
	void extend(int c,int id){
		int cur=++sz,p=last,q; len[last=cur]=len[p]+1,pos[id]=cur;
		for(;~p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;
		if(p==-1) fa[cur]=0;
		else if(len[q=ch[p][c]]==len[p]+1) fa[cur]=q;
		else{
			int clone=++sz; len[clone]=len[p]+1;
			memcpy(ch[clone],ch[q],sizeof ch[q]),fa[clone]=fa[q],fa[cur]=fa[q]=clone;
			for(;~p&&ch[p][c]==q;p=fa[p]) ch[p][c]=clone;
		}
	}
	void dfs1(int u){
		st[0][dfn[u]=++tim]=len[u];
		for(int v:G[u]) dfs1(v),st[0][++tim]=len[u];
	}
	void ST(){
		for(int i=1;i<=sz;i++) G[fa[i]].push_back(i);
		dfs1(0);
		for(int i=2;i<=tim;i++) lg[i]=lg[i>>1]+1;
		for(int j=1;j<=Log;j++)
			for(int i=1,l=1<<j;i+l-1<=tim;i++)
				st[j][i]=min(st[j-1][i],st[j-1][i+(l>>1)]);
	}
	void dfs2(int u){
		for(int v:G[u]) dfs2(v),merge(rt[u],rt[u],rt[v]);
		if(u) ans+=(len[u]-len[fa[u]])*sum[rt[u]];
	}
	void calc(){
		for(int i=1;i<=sz;i++) G[fa[i]].push_back(i);
		dfs2(0);
	}
}S,RS;
char s[maxn];
int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++) S.extend(s[i]-'a',i),ans+=i-S.len[S.fa[S.last]],i==n-1&&(ans<<=1);//s and s*
	for(int i=n;i>=1;i--) RS.extend(s[i]-'a',i),i>1&&(ans+=n-i+1-RS.len[RS.fa[RS.last]]);//*t
	RS.ST();
	for(int i=1;i<=n-2;i++) ins(rt[S.pos[i]],1,tim,dfn[RS.pos[i+2]]);
	S.calc();
	printf("%lld\n",ans+2);
}