【Codeforces 700E】Cool Slogans
后缀自动机，线段树合并。
题目大意：
给定一个字符串 $S$，要求构造字符串序列 $s_1,s_2,\ldots,s_k$，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i\in[2,n]$，都有 $s_i$ 在 $s_{i-1}$ 中出现了至少 $2$ 次（可以有重叠部分，只要起始、结尾位置不同即可）。
求可能的最大的 $k$ 的值（即序列的最大可能长度）。
题解：
存在一种构造方式，满足 $s_i$ 是 $s_{i-1}$ 的后缀。若最优方案不满足上述条件，则可以在所有不是后缀的转移处将后缀同时删掉，不影响答案。因此只需考虑后缀。
考虑对原串建 SAM，并建出 parent 树。在 parent 树上，祖先结点代表的串是后代的后缀。
考虑在 parent 树上 dp，令 $f_i$ 表示以结点 $i$ 代表的最长串（以下简称 $i$ 串）作为 $s_1$ 的最大的 $k$ 的值。结点 $i$ 可以向后代（不一定是儿子）进行转移。
$u$ 能转移到 $v$ 的条件为，$v$ 串中，$u$ 串至少出现 $2$ 次。那么只要在 $u$ 的 right 集合中，$[pos_v-len_v+len_u,pos_v]$ 中存在至少两个结点，就说明出现了至少 $2$ 次（$pos_i$ 为 $i$ 的 right 集合中任意一个点）。
用线段树合并得到每个结点的 right 集合，可以 $O(\log n)$ 完成一次查询。
考虑记 $g_x$ 表示 $x$ 的祖先中，最上面的那个不能向 $x$ 转移的点。我们求 $g_x$ 的时候，用 $g_{fa_x}$ 的值继续往下考虑（因为在 $x$ 串的子串中出现了至少 $2$ 次，在 $x$ 串中也至少出现 $2$ 次）。直接暴力跳儿子并判断就行了，遇到不符合条件就停止。由于一个点作为 $x$，开始时会判一次，然后一个点作为 $g_x$，不考虑开始时第一次判断，只会不符合条件判一次，符合条件判一次，因此总判断次数为 $O(n)$。
总时间复杂度 $O(n\log n)$。
Code：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=4e5+5;
int n;
int up[N],F[N];
char s[N];
int rt[N];
int sz[N*70],ls[N*70],rs[N*70],nod,head[N],cnt,rgt[N];
struct edge{
int to,nxt;
}e[N];
void add(int&o,int l,int r,const int&pos){
if(!o)o=++nod;
++sz[o];
if(l<r){
const int mid=l+r>>1;
if(pos<=mid)add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos);
}
}
int merge(int ld,int rd){
if(!ld||!rd)return ld|rd;
int ret=++nod;
ls[ret]=merge(ls[ld],ls[rd]);
rs[ret]=merge(rs[ld],rs[rd]);
sz[ret]=sz[ls[ret]]+sz[rs[ret]];
return ret;
}
int query(int o,int l,int r,const int&L,const int&R){
if(!o||L>R)return 0;
if(L<=l&&r<=R)return sz[o];
const int mid=l+r>>1;
if(L<=mid&&mid<R)return query(ls[o],l,mid,L,R)+query(rs[o],mid+1,r,L,R);
if(L<=mid)return query(ls[o],l,mid,L,R);
return query(rs[o],mid+1,r,L,R);
}
int ch[N][26],len[N],lst=1,fa[N],tot=1;
void ins(int pos,char c){
c-='a';
int p=lst,np=lst=++tot;
add(rt[np],1,n,pos);
rgt[np]=pos;
len[np]=len[p]+1;
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
if(!p)fa[np]=1;else{
int q=ch[p][c];
if(len[q]==len[p]+1)fa[np]=q;else{
int nq=++tot;
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof*ch);
fa[nq]=fa[q],fa[np]=fa[q]=nq;
for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
}
}
void DFS(int now){for(int i=head[now];i;i=e[i].nxt)DFS(e[i].to),rgt[now]=max(rgt[now],rgt[e[i].to]),rt[now]=merge(rt[now],rt[e[i].to]);}
void dfs(int now){
for(int&i=head[now];i;i=e[i].nxt){
const int&v=e[i].to;
int&x=up[v];
x=up[now];
while(query(rt[x],1,n,rgt[v]-len[v]+len[x],rgt[v]-1))x=e[head[x]].to;
F[v]=F[fa[x]]+1;
dfs(v);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>(s+1);
for(int i=1;i<=n;++i)ins(i,s[i]);
for(int i=tot;i;--i)
if(fa[i])
e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt,
up[1]=1;
DFS(1);
dfs(1);
cout<<*max_element(F+1,F+tot+1)<<'\n';
return 0;
}