CF1063F
tag：Suffix Tree，Dp
定义字符串数组 \(t_{1\dots k}\) 合法当且仅当 \(t_{i}\) 是 \(t_{i-1}\) 的字串且 \(t_i\ne t_{i-1}\)
给定字符串 \(s\)，求最大的 \(k\) 使得可以将 \(s\) 提取出 \(k\) 个不相交的区间，依次排序后得到的字符串数组合法。
\(|s|\le 5\times 10^5\)
Solution
最优决策下我们必然让长度单调递减，每次恰好减 \(1\)。
枚举区间 \([i,j]\)，然后连边，我们可以做到 \(\mathcal O(n^3)\) 的连边，然后就是一个 DAG 最长路的问题了。
进一步观察，我们每个串可以用后缀树上一个节点 \(\rm +~end\) 的位置表示。
注意到长度上界至多为 \(1+2+...+cnt=|s|\)，即 \(cnt=\sqrt{|s|}\)，于是我们可以得到一个 \(\mathcal O(|s|\sqrt{|s|})\) 的做法。
实际上最优决策是固定的，每种字符都会被固定在一个合法的最右点。
好像非常有道理：
设 \(f_i\) 表示以 \(i\) 为结尾最长合法的字符串数组。
直觉上从后往前让 \(f_i\) 增加就好了。
于是转移为 \(f_i=\max(f_{j})+1,j\ge i+f_i,s_{j-f_j+1...j}\subseteq s_{i-f_i+1...i}\)
接下来可以证明 \(f_{i}\ge f_{i+1}-1\)
将 \(i+1\) 的结尾删去之后显然 \(f_i\) 是合法的。
于是不难得到做法，从后往前 Dp，每个 \(f_i\) 从 \(f_{i+1}-1\) 开始枚举长度 \(L\)，那么只需要 check，对于长度 \(L\)，我们只需要检查是否存在字符 \([i+L,n]\)
然后可以考虑在移动的时候暴力维护 \(r\) 的移动...大概就没了吧？
然而仔细做了一下，这样貌似非常不好做...
于是只能改成 Dp 状态，设为 \(f_i\) 表示以 \(i\) 为开头的最长的答案。
不难得到 \(f_{i+1}\ge f_i-1\)，于是得到 \(f_i\le f_{i+1}+1\)
于是需要 check 的区间就是 \(i+f_i\) 这段区间，不难注意到这个值是不增的，所以直接扫就可以了！
\(Code:\)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 1e6 + 5 ;
const int inf = 1e9 + 7 ;
const int Inf = 1e8 + 7 ;
struct SuffixTree {
int lef, len, lk ;
int ch[28] ;
} t[N] ;
int tr[N << 2], m, n, cnt = 1, bef = 1, rem ;
int Id[N], idx, L[N], R[N], f[N], fa[N][19], dep[N] ;
char s[N] ;
int node(int l, int len) { t[++ cnt].lk = 1, t[cnt].lef = l, t[cnt].len = len ; return cnt ; }
int query( int x, int l, int r, int ql, int qr ) {
if( ql <= l && r <= qr ) return tr[x] ;
if( ql > r || qr < l ) return 0 ;
int mid = ( l + r ) >> 1 ;
return max(query(ls(x), l, mid, ql, qr), query(rs(x), mid + 1, r, ql, qr)) ;
}
void update( int x, int l, int r, int k, int d ) {
if( l == r ) { tr[x] = d ; return ; }
int mid = ( l + r ) >> 1 ;
if( mid >= k ) update( ls(x), l, mid, k, d ) ;
else update( rs(x), mid + 1, r, k, d ) ;
tr[x] = max( tr[ls(x)], tr[rs(x)] ) ;
}
void insert(int x) {
++ m, s[x] -= 'a' ; int u = s[x], lst = 1 ; ++ rem ;
while( rem ) {
while( rem > t[t[bef].ch[s[m - rem + 1]]].len )
rem -= t[bef = t[bef].ch[s[m - rem + 1]]].len ;
int &d = t[bef].ch[s[m - rem + 1]], c = s[t[d].lef + rem - 1] ;
if( u == c || !d ) {
t[lst].lk = bef, lst = bef ;
if( !d ) d = node( m - rem + 1, inf ) ;
else return ;
} else {
int np = node(t[d].lef, rem - 1) ;
t[np].ch[u] = node(m, inf), t[np].ch[c] = d,
t[d].lef += (rem - 1), t[d].len -= (rem - 1),
t[lst].lk = d = np, lst = d ;
} (bef == 1) ? -- rem : bef = t[bef].lk ;
}
}
void dfs( int x, int ff, int d ) {
L[x] = ++ idx ;
fa[x][0] = ff ; rep( i, 1, 17 ) fa[x][i] = fa[fa[x][i - 1]][i - 1] ;
if( t[x].len > Inf ) {
t[x].len = n + 1 - t[x].lef, d += t[x].len, Id[n - d + 1] = x ; dep[x] = d ;
return ;
}
d += t[x].len ; int v ; dep[x] = d ;
rep( i, 0, 26 ) if( v = t[x].ch[i] ) dfs( v, x, d ) ;
R[x] = idx ;
}
int Get( int l, int le ) {
int x = Id[l] ;
drep( i, 0, 17 ) if(dep[fa[x][i]] >= le) x = fa[x][i] ;
return x ;
}
signed main()
{
n = gi(), scanf("%s", s + 1 ), t[0].len = inf, s[++ n] = 'z' + 1 ;
rep( i, 1, n ) insert(i) ; -- n ;
dfs(1, 1, 0) ; int r = n + 1 ; f[n + 1] = 0 ; t[1].len = 0 ;
for( re int i = n; i >= 1; -- i ) {
for( re int j = f[i + 1] + 1; j > 0; -- j ) {
int l = i + j ;
if( r > l ) -- r, update( 1, 1, idx, L[Id[r]], f[r] ) ;
int u = Get(i, j - 1) ;
int mx = query(1, 1, idx, L[u], R[u] ) ;
u = Get(i + 1, j - 1) ;
mx = max( mx, query(1, 1, idx, L[u], R[u]) ) ;
if( mx >= j - 1 ) { f[i] = j ; break ; }
}
}
int ans = 0 ;
rep( i, 1, n ) ans = max( ans, f[i] ) ;
cout << ans << endl ;
return 0 ;
}