CF700E Cool Slogans 做题记录
https://www.luogu.com.cn/problem/CF700E
首先条件可以转化为，\(s_i\) 必须是 \(s_{i-1}\) 的 border，否则 \(s_i\) 可以缩短且不是变劣。
子串是后缀的前缀，所以在后缀上考虑。设 \(s_i\) 为 \(s[i:n]\) cool 值最大的前缀，\(f_i\) 为 \(s_i\) 的 cool 值。
从后向前转移，若 \(j<i\) 且 \(LCP(s[i:n],s[j:n])\ge |s_i|\)，那么 \(f_i\) 可以转移到 \(f_j\)。显然要同时保证 \(|s_i|\) 最小。
设 \(len_i=|s_i|\)。如果直接跟随 \(f_i\) 转移 \(len_i\)，可能会出现缩小 \(f_i\) 增大 \(len_i\) 可以得到更优转移的情况。
但我们发现，若 \(f_i\) 是由 \(f_k\) 转移而来，那么令 \(f_i\) 缩小 \(1\)，对应的 \(s_i\) 就会变为 \(s_k\)，向前转移 \(len_j\) 时就比 \(k\) 要优了。
我们再设一个 \(g_i\) 表示使得 $f_i $ 最大的 \(j\) 的 \(len_j\) 最小是多少。\(i\) 向前转移到的后缀在 SA 上是一段区间，可以线段树维护。处理每个 \(i\) 时，若 \(f_i=1\) 则 \(len_i=1\)；否则，找到 \(LCP(s[i:n],s[p:n])\ge g_i\) 的最小 \(p\)，更新 \(len_i=g_i+p-i\)。然后继续在线段树上向前转移。
int n;
char a[N];
int sa[N],rk[N],cnt[N],ht[N],tp[N];
int st[N][22],lg[N];struct Info{int x,len;bool operator<(const Info& tmp)const{return x<tmp.x||(x==tmp.x&&len>tmp.len);}bool operator>(const Info& tmp)const{return x>tmp.x||(x==tmp.x&&len<tmp.len);}
};struct SegNode{Info info;int mn;
}tr[N<<2];void Pushup(int p){tr[p].mn=min(tr[p<<1].mn,tr[p<<1|1].mn);
}void Buildtr(int p,int l,int r){tr[p].info=Info{1,1};tr[p].mn=IINF;if(l==r) return;int mid=(l+r)>>1;Buildtr(p<<1,l,mid);Buildtr(p<<1|1,mid+1,r);
}void Chkmax(int p,int l,int r,int L,int R,Info v){if(L<=l&&r<=R) return Ckmax(tr[p].info,v),void();int mid=(l+r)>>1;if(L<=mid) Chkmax(p<<1,l,mid,L,R,v);if(R>mid) Chkmax(p<<1|1,mid+1,r,L,R,v);
}void Update(int p,int l,int r,int x,int v){if(l==r) return Ckmin(tr[p].mn,v),void();int mid=(l+r)>>1;if(x<=mid) Update(p<<1,l,mid,x,v);else Update(p<<1|1,mid+1,r,x,v);Pushup(p);
}Info Askinfo(int p,int l,int r,int x){if(l==r) return tr[p].info;int mid=(l+r)>>1; Info res=tr[p].info;if(x<=mid) return max(res,Askinfo(p<<1,l,mid,x));else return max(res,Askinfo(p<<1|1,mid+1,r,x));
}int Askpos(int p,int l,int r,int L,int R){if(L<=l&&r<=R) return tr[p].mn;int mid=(l+r)>>1,res=IINF;if(L<=mid) Ckmin(res,Askpos(p<<1,l,mid,L,R));if(R>mid) Ckmin(res,Askpos(p<<1|1,mid+1,r,L,R));return res;
}void SolveSA(){int m='z';for(int i=1;i<=n;i++) rk[i]=a[i],cnt[rk[i]]++;for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i;i--) sa[cnt[rk[i]]--]=i;for(int k=1;k<=n;k<<=1){int p=0;for(int i=n-k+1;i<=n;i++) tp[++p]=i;for(int i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k;for(int i=1;i<=m;i++) cnt[i]=0;for(int i=1;i<=n;i++) ++cnt[rk[i]];for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i;i--) sa[cnt[rk[tp[i]]]--]=tp[i];memcpy(tp,rk,sizeof(tp));rk[sa[1]]=m=1;for(int i=2;i<=n;i++){if(tp[sa[i]]==tp[sa[i-1]]&&tp[min(n+1,sa[i]+k)]==tp[min(n+1,sa[i-1]+k)]) rk[sa[i]]=rk[sa[i-1]];else rk[sa[i]]=++m;} if(m==n) break;}for(int i=1;i<=n;i++){ht[rk[i]]=max(0,ht[rk[i-1]]-1);while(a[i+ht[rk[i]]]==a[sa[rk[i]-1]+ht[rk[i]]]) ++ht[rk[i]];}for(int i=1;i<=n;i++) st[i][0]=ht[i];for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;for(int j=1;j<=lg[n];j++){for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);}
}int Askst(int l,int r){int x=lg[r-l+1];return min(st[l][x],st[r-(1<<x)+1][x]);
}int LCP(int x,int y){if(x==y) return n-x+1;if(rk[x]>rk[y]) swap(x,y);return Askst(rk[x]+1,rk[y]);
}pii Askrange(int x,int k){int l=x,r=n,L=x,R=x;while(l<=r){int mid=(l+r)>>1;if(LCP(sa[x],sa[mid])>=k) R=mid,l=mid+1;else r=mid-1; }l=1,r=x;while(l<=r){int mid=(l+r)>>1;if(LCP(sa[x],sa[mid])>=k) L=mid,r=mid-1;else l=mid+1; }return {L,R};
}signed main(){read(n);scanf("%s",a+1);n=strlen(a+1);SolveSA();Buildtr(1,1,n);int ans=0; for(int i=n;i;i--){Info info=Askinfo(1,1,n,rk[i]);int f=info.x,l=info.len;Ckmax(ans,f);if(f>1){pii seg=Askrange(rk[i],l);l+=Askpos(1,1,n,seg.first,seg.second)-i;}pii seg=Askrange(rk[i],l);Chkmax(1,1,n,seg.first,seg.second,Info{f+1,l});Update(1,1,n,rk[i],i);}printf("%d\n",ans);return 0;
}