[NOI2015]品酒大会 [SAM]

[NOI2015]品酒大会 [SAM]

​​传送门​​

其实没有想象中难, 我们知道, 两个串的最长公共后缀就是 parent 树上的LCA 的len

对于出现次数, 枚举每一个 LCA, 然后 siz 乘一下

因为如果 len 出现了, len - 1 也出现了, 所以求一个后缀和

对于最大值, 我们维护子树最大与次大, 因为有负数, 所以还要维护次小与最小

同样对最大值也求一个后缀最大

#include#define N 600050using namespace std;typedef long long ll;const ll inf = 900000000000000000;int n; char s[N]; ll a[N];struct Node{ int ch[26], link, len, siz;} t[N];ll mx1[N], mx2[N], mi1[N], mi2[N];ll sum[N], ans[N];int last, tot;void Extend(int Id, int c){ int cur = ++tot, p = last; mx1[cur] = a[Id]; mx2[cur] = -inf; mi1[cur] = a[Id]; mi2[cur] = inf; t[cur].len = t[p].len + 1; t[cur].siz = 1; for(;p && !t[p].ch[c]; p = t[p].link) t[p].ch[c] = cur; if(!p) t[cur].link = 1; else{ int q = t[p].ch[c]; if(t[q].len == t[p].len + 1) t[cur].link = q; else{ int clone = ++tot; mx1[clone] = mx2[clone] = -inf; mi1[clone] = mi2[clone] = inf; t[clone].link = t[q].link; t[clone].len = t[p].len + 1; for(int i=0; i<26; i++) t[clone].ch[i] = t[q].ch[i]; for(;p && t[p].ch[c] == q; p = t[p].link) t[p].ch[c] = clone; t[cur].link = t[q].link = clone; } } last = cur;}vector v[N];void mxUpt(ll w, int u){ if(w > mx1[u]) mx2[u] = mx1[u], mx1[u] = w; else if(w > mx2[u]) mx2[u] = w;}void miUpt(ll w, int u){ if(w < mi1[u]) mi2[u] = mi1[u], mi1[u] = w; else if(w < mi2[u]) mi2[u] = w;}void dfs(int u){ for(int i=0; i=1; i--) Extend(i, s[i] - 'a'); for(int i=2; i<=tot; i++) v[t[i].link].push_back(i); for(int i=1; i<=tot; i++) ans[i] = -inf; dfs(1); for(int i=n-1; i>=0; i--) ans[i] = max(ans[i], ans[i+1]), sum[i] += sum[i+1]; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。