本文主要是介绍[NOI2015]品酒大会 [SAM]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
其实没有想象中难, 我们知道, 两个串的最长公共后缀就是 parent 树上的LCA 的len
对于出现次数, 枚举每一个 LCA, 然后 siz 乘一下
因为如果 len 出现了, len - 1 也出现了, 所以求一个后缀和
对于最大值, 我们维护子树最大与次大, 因为有负数, 所以还要维护次小与最小
同样对最大值也求一个后缀最大
#include<bits/stdc++.h>
#define N 600050
using 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<int> 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<v[u].size(); i++){int son = v[u][i]; dfs(son);sum[t[u].len] += 1ll * t[u].siz * t[son].siz;t[u].siz += t[son].siz;mxUpt(mx1[son], u); mxUpt(mx2[son], u);miUpt(mi1[son], u); miUpt(mi2[son], u);} if(t[u].siz < 2) return;if(mx2[u] != -inf && mi2[u] != inf) ans[t[u].len] = max(ans[t[u].len], max(mx1[u] * mx2[u], mi1[u] * mi2[u]));
}
int main(){scanf("%d%s", &n, s+1); last = tot = 1; mx1[1] = mx2[1] = -inf; mi1[1] = mi2[1] = inf;for(int i=1; i<=n; i++) scanf("%lld", &a[i]);for(int i=n; 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<n; i++){printf("%lld %lld\n", sum[i], sum[i] ? ans[i] : 0);} return 0;
}
这篇关于[NOI2015]品酒大会 [SAM]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
