Codeforces 700E Cool Slogans
题目大意：给出一个字符串 (S)，让你构造一个序列 (S_1,S_2dots S_k)，满足 (forall S_i) (S_i) 是 (S) 的字串，且对于 (i > 1) ，(S_i) 在 (S_{i-1}) 中出现了至少两次，最大化 (k) 的长度。(|S|leq 2 imes 10^5)。
解题思路：
可以证明一个很牛逼的结论，对于 ( ext{parents}) 树上的一个节点 (u) ，其在其子树中的任意节点 (v) 代表的串 (maxv) ，节点 (u) 代表的所有串在 (maxv) 中的所有串出现次数相同。
假设有两个串出现次数不同，那么一定存在一个出现位置使得 (u) 代表的一个串 (k) 是 (maxv) 的前缀但是 (maxu) 不是，这样会发现 (maxu) 和 (k) 的 ( ext{right}) 集合不同，矛盾。
那么有了这个结论每个节点随便选个长度代表它都是一样的，显然每个串选 (maxu) 对于其祖先来说最优，然后就可以在 (parent) 拿节点做状态了。
贪心地从后往前做，相当于在 (parent) 树从根往下做能放就放，正确性显然。令 (f[u]) 表示当前考虑到 (u) 节点的最长答案，那么只需要判断 (u) 节点的 (max) 能否放在上一个选的串前面即可。由于 (right) 集合是一个等价类，那么对于每个串的所有出现位置只需要取最前面一个即可，然后用线段树合并维护 (right) 集合判断上一个串是否出现两次即可。由于上一个串是 (u) 的一个祖先，还需要记一下上一个选的串对应节点是什么，复杂度 (O(|S|logn))。
code
/*program by mangoyang*/
#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int ch = 0, f = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 400005;
char s[N]; int n, ans;
namespace Seg{
#define mid ((l + r) >> 1)
int lc[N*25], rc[N*25], sz[N*25], size;
inline void ins(int &u, int l, int r, int pos){
if(!u) u = ++size;
if(l == r) return (void) (sz[u]++);
if(pos <= mid) ins(lc[u], l, mid, pos);
else ins(rc[u], mid + 1, r, pos);
sz[u] = sz[lc[u]] + sz[rc[u]];
}
inline int merge(int x, int y, int l, int r){
if(!x || !y) return x + y;
int o = ++size;
if(l == r) sz[o] = sz[x] + sz[y];
else{
lc[o] = merge(lc[x], lc[y], l, mid);
rc[o] = merge(rc[x], rc[y], mid + 1, r);
sz[o] = sz[lc[o]] + sz[rc[o]];
}
return o;
}
inline int query(int u, int l, int r, int L, int R){
if(l >= L && r <= R) return sz[u];
int res = 0;
if(L <= mid) res += query(lc[u], l, mid, L, R);
if(mid < R) res += query(rc[u], mid + 1, r, L, R);
return res;
}
#undef mid
}
namespace SAM{
vector<int> g[N];
int ch[N][26], id[N], len[N], fa[N], dp[N], rt[N], pos[N], tail = 1, size = 1;
inline int newnode(int x){ return len[++size] = x, size; }
inline void ins(int c, int x){
int p = tail, np = newnode(len[p] + 1); pos[np] = x;
Seg::ins(rt[np], 1, n, pos[np]);
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) return (void) (fa[np] = 1, tail = np);
int q = ch[p][c];
if(len[q] == len[p] + 1) fa[np] = q;
else{
int nq = newnode(len[p] + 1); pos[nq] = x;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(int i = 0; i < 26; i++) ch[nq][i] = ch[q][i];
for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}tail = np;
}
inline void addedge(){
for(int i = 2; i <= size; i++) g[fa[i]].push_back(i);
}
inline void dfs(int u){
for(int i = 0; i < (int) g[u].size(); i++)
dfs(g[u][i]), rt[u] = Seg::merge(rt[u], rt[g[u][i]], 1, n);
}
inline void dfs2(int u){
if(u > 1){
if(fa[u] == 1) id[u] = u, dp[u] = 1;
else{
int tmp = Seg::query(rt[id[fa[u]]], 1, n, pos[u] - len[u] + len[id[fa[u]]], pos[u] - 1);
if(tmp) dp[u] = dp[fa[u]] + 1, id[u] = u; else dp[u] = dp[fa[u]], id[u] = id[fa[u]];
}
}
ans = max(ans, dp[u]);
for(int i = 0; i < (int) g[u].size(); i++) dfs2(g[u][i]);
}
}
int main(){
read(n), scanf("%s", s + 1);
for(int i = 1; i <= n; i++)
SAM::ins(s[i] - 'a', i);
SAM::addedge(), SAM::dfs(1), SAM::dfs2(1);
cout << ans << endl;
return 0;
}