CF700E Cool Slogans
这是一道用后缀数组优化DP的神题，所以我们必须先抛开后缀数组，从DP的角度来想题。
首先，我们发现，对于一组合法的s_1,\dots,s_n，我们一定可以掐头去尾，使得s_i是s_{i-1}的\text{Border}，即首尾的一个相同子串。这很好理解——因为掐头去尾剩下的东西一定是原来的一个子串，而s_i本来就在s_{i-1}中出现了两次，故s_i的子串，无论掐成啥样，都必定会在s_{i-1}中仍然出现两次。
于是我们就可以设想DP状态了：令f_i表示以第i个字符开头的所有子串中，最多能套娃几层\text{Border}。则答案即为\max\limits_{i=0}^{n-1}f_i。
我们考虑如何求出f_i。显然，它的DP顺序应该是倒着的，因为长串只能由短串转移而来。
于是我们就可以设想出一种DP方程出来：
这启发我们要记录一个$len_j$表示上述的$\text{Border}$长度。显然，这个$len_j$应是**越短越好**。
则我们的转移条件即为：$i<j\ \land\ \operatorname{LCP}(i,j)\geq len_j$。
------------
但我们应该想想，**这真的是充分必要条件吗**？如果$\operatorname{LCP}(i,j)<len_j$，就不可以转移了吗？这时候，如果我们适当减小$f_j$的话，它对应的$len_j$也会跟着减小，最终就有可能减小到$\leq\operatorname{LCP}$的地步，就可以转移了。那是不是我们对于每个$j$，就要二分出来可以转移的$f_j$了呢？
这看上去很有道理的样子——但我们的担心实际上**完全是多余**的。$f_j$的减小，就意味着$\text{Border}$套娃层数的减小。而套娃次数更少的状态，实际上**被保存在了其它位置**。
例如，我们有这样一条关系：$f_j\leftarrow f_k$，即$k$转移到$j$。
现在我们想尝试用$j$转移到$i$去，但发现$\operatorname{LCP}$太短不够。于是我们减小$f_j$。
但是$f_j$一减小，就相当于**退化成$f_k$了**，而$f_k$的状态，我们是**有备份的**，即$k$本身，它也可以转移到$i$去。因此，我们不用担心更小的$f_j$是否更优——它的祖先会解决这个问题的。
------------
好的我们现在回到转移本身。很明显$len_j$也是一个需要维护的值。或许你们会认为$len_i$可以同$f_i$一起转移。即，我们先求出$f_i$，然后找出所有$f_j=f_i-1$的位置，然后尝试用$len_j$更新$len_i$。
但是这又有问题了——之前我们减小$f_j$的想法，是否在这里就会实现？
例如，我们这里还是有一条$f_j\leftarrow f_k$。
现在我们又想转移$i$了。但是$j$仍然转移不了，我们就被迫从$f_k$转移来。显然，这里的$len_i$长度就应该是$k-i+len_k$。
但是，如果它可以从$j$转移来的话（当然$f_j$应该减小到$f_i-1$的大小），长度很有可能就成为了$j-i+len_j$。显然这个$len_j$应该等于$len_k$，毕竟$k$是$j$的祖先，则如果它们套娃层数一致，长度就应该一致。
而又应有$j<k$，故实际上$j-i+len_j<k-i+len_k$，应该从$j$转移而不是从$k$转移。
我们发现，之前在$f$的转移中不起效的情况，在这里却又起效了。应该如何应对呢？
------------
先从$len$的部分缓缓，我们先回到求出$f_i$的过程。这里我们又有两种想法，即填表法（由$i$考虑所有合法的$j$）与刷表法（由$j$转移到所有能转移的$i$）。如果我们选择前一种的话，不同的$j$的$\operatorname{LCP}$变化毫无规律，不好转移；而如果选择后一种，因为我们已经固定了$len_j$，所以我们只需要求出所有$\operatorname{LCP}(i,j)\geq len_j$的位置即可。依据$\text{LCP Lemma}$，这在后缀数组中**是从$rk_i$出发向左向右的一段区间**。于是我们只需要在后缀数组上二分求出这段区间，然后用线段树进行区间取$\max$即可。
然后我们就要考虑求出$len_i$了。显然，在求出$f_i$的过程中，我们可以顺手求出$len_j$，即所有$f_j=f_i-1$的$j$中，最小的$len$。这便是我们上文中“$len_j$应该等于$len_k$”那句话中，那个始终不变的$len_j$。我们仍然可以找出$\operatorname{LCP}(i,j)\geq len_j$的区间，然后找到区间里最小的那个$j$，则有$len_i=j-i+len_j$。关于区间里最小的$j$，因为我们同时还要要求$j>i$，所以仍然必须得用线段树实现。
则时间复杂度为$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=200100;
int res;
namespace Suffix_Array{
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,LG[N],mn[N][20];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
int LCP(int x,int y){
if(x>y)swap(x,y);
x++;
int k=LG[y-x+1];
return min(mn[x][k],mn[y-(1<<k)+1][k]);
}
void Range(int x,int len,int &L,int &R){//ask for the range of elements that LCP[x,i]>=len is held.
x=rk[x];
int l,r;
l=0,r=x;
while(l<r){
int mid=(l+r)>>1;
if(LCP(mid,x)>=len)r=mid;
else l=mid+1;
}
L=r;
l=x,r=n-1;
while(l<r){
int mid=(l+r+1)>>1;
if(LCP(mid,x)>=len)l=mid;
else r=mid-1;
}
R=l;
}
}
using namespace Suffix_Array;
struct SegTree{
int f,len;
SegTree(){f=1,len=1;}
SegTree(int A,int B){f=A,len=B;}
friend bool operator<(const SegTree &x,const SegTree &y){
if(x.f!=y.f)return x.f<y.f;
return x.len>y.len;
}
};
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
namespace SG1{
SegTree tag[N<<2];
#define pushdown(x) tag[lson]=max(tag[lson],tag[x]),tag[rson]=max(tag[rson],tag[x]),tag[x]=SegTree()
void modify(int x,int l,int r,int L,int R,SegTree sg){
if(l>R||r<L)return;
if(L<=l&&r<=R){tag[x]=max(tag[x],sg);return;}
pushdown(x),modify(lson,l,mid,L,R,sg),modify(rson,mid+1,r,L,R,sg);
}
SegTree query(int x,int l,int r,int P){
if(l==r)return tag[x];
pushdown(x);
return (P<=mid)?query(lson,l,mid,P):query(rson,mid+1,r,P);
}
}
namespace SG2{
int mn[N<<2];
void pushup(int x){mn[x]=min(mn[lson],mn[rson]);}
void modify(int x,int l,int r,int P){
if(l>P||r<P)return;
if(l==r){mn[x]=sa[P];return;}
modify(lson,l,mid,P),modify(rson,mid+1,r,P),pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(l>R||r<L)return 0x3f3f3f3f;
if(L<=l&&r<=R)return mn[x];
return min(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
}
}
int main(){
scanf("%d%s",&n,s),m='z',SA(),memset(SG2::mn,0x3f,sizeof(SG2::mn));
for(int i=n-1,L,R;i>=0;i--){
SegTree tmp=SG1::query(1,0,n-1,rk[i]);
res=max(res,tmp.f);//in this phase, f is the real f, while len is still the former status'.
if(tmp.f!=1){//need to get the real len.
Range(i,tmp.len,L,R);
tmp.len+=SG2::query(1,0,n-1,L,R)-i;
}
tmp.f++;
Range(i,tmp.len,L,R);
SG1::modify(1,0,n-1,L,R,tmp);
SG2::modify(1,0,n-1,rk[i]);
}
printf("%d\n",res);
return 0;
}
```