「LOJ 2133」「NOI2015」品酒大会

发表于

一年一度的「幻影阁夏日品酒大会」隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发「首席品酒家」和「首席猎手」两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 nn 杯鸡尾酒。这 nn 杯鸡尾酒排成一行，其中第 ii 杯酒 （1≤i≤n1 \leq i \leq n） 被贴上了一个标签 sis_i ，每个标签都是 2626 个小写英文字母之一。设 Str(l,r)\mathrm{Str}(l, r) 表示第 ll 杯酒到第 rr 杯酒的 r−l+1r-l+1 个标签顺次连接构成的字符串。若 Str(p,p0)=Str(q,q0)\mathrm{Str}(p, p_0) = \mathrm{Str}(q, q_0) ，其中 1≤p≤p0≤n1 \leq p \leq p_0 \leq n ， 1≤q≤q0≤n1 \leq q \leq q_0 \leq n ， p≠qp \neq q ， p0−p+1=q0−q+1=rp_0-p+1=q_0-q+1=r ，则称第 pp 杯酒与第 qq 杯酒是「 rr 相似」的。当然两杯「 rr 相似」（ r>1r > 1 ）的酒同时也是「 11 相似」、「 22 相似」、 $\cdots $ 、「 r−1r-1 相似」的。特别地，对于任意的 1≤p,q≤n1 \leq p, q \leq n ， p≠qp \neq q ，第 pp 杯酒和第 qq 杯酒都是「 00 相似」的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了「首席品酒家」的称号，其中第 ii 杯酒 （ 1≤i≤n1 \leq i \leq n ） 的美味度为 aia_i 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 pp 杯酒与第 qq 杯酒调兑在一起，将得到一杯美味度为 ap⋅aqa_p \cdot a_q 的酒。现在请各位品酒师分别对于 r=0,1,2,⋯n−1r=0,1,2,\cdots n-1 ， 统计出有多少种方法可以选出两杯「 rr 相似」的酒，并回答选择两杯「 rr 相似」的酒调兑可以得到的美味度的最大值。

Constraints

n≤300000n\leq 300000 ， ∣ai∣≤109|a_i|\leq 10^9

Solution

题意中的「 rr 相似」即为两个后缀的最长公共前缀，等价于倒着建的后缀自动机 parent 树上的 lca 。

我们需要在 parent 树上统计以下信息：子树有效节点个数，子树内最大值，子树内次大值，子树内最小值，子树内次小值。

每到达一个节点，将来自两个不同儿子的有效节点两两组合的和，就是恰好「 deepdeep 相似」的答案，可以利用差分来更新到 「 11 相似」到「 deepdeep 相似」的答案里。同时，用最大值 $\cdot $ 次大值和最小值 $\cdot $ 次小值更新美味度的答案，可以用树状数组倒过来实现。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=6e5+5;
const LL inf=-1e18-1;
int n,last,size,root,cnt;
int a[N],first[N],sz[N],w[N];
int mx[N],cmx[N],mn[N],cmn[N];
LL tmp,tr[N],num[N],ans[N];
char ch[N];
struct SAM{int mx,fa,ch[26];}t[N];
struct edge{int to,next;}e[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void add(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void ins(int c,int pos)
{
	int np=++size;
	sz[np]=1;w[np]=a[pos];
	t[np].mx=t[last].mx+1;
	int x=last;last=np;
	while(x&&!t[x].ch[c])t[x].ch[c]=np,x=t[x].fa;
	if(!x)t[np].fa=root;
	else
	{
		int y=t[x].ch[c];
		if(t[y].mx==t[x].mx+1)t[np].fa=y;
		else
		{
			int nq=++size;t[nq]=t[y];
			t[nq].mx=t[x].mx+1;
			t[y].fa=t[np].fa=nq;
			while(x&&t[x].ch[c]==y)t[x].ch[c]=nq,x=t[x].fa;
		}
	}
}
int lowbit(int x){return x&(-x);}
void modify(int x,LL v){for(;x<=n;x+=lowbit(x))tr[x]=max(tr[x],v);}
LL query(int x){LL ans=inf;for(;x;x-=lowbit(x))ans=max(ans,tr[x]);return ans;}
void dfs(int x)
{
	int deep=t[x].mx;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;dfs(to);
		num[deep]+=1ll*sz[x]*sz[to];sz[x]+=sz[to];
		if(mn[to]<mn[x])cmn[x]=mn[x],mn[x]=mn[to];
		else if(mn[to]<cmn[x])cmn[x]=mn[to];
		if(mx[to]>mx[x])cmx[x]=mx[x],mx[x]=mx[to];
		else if(mx[to]>cmx[x])cmx[x]=mx[to];
	}
	if(cmn[x]!=1e9+1)modify(n-deep,1ll*cmn[x]*mn[x]);
	if(cmx[x]!=-1e9-1)modify(n-deep,1ll*cmx[x]*mx[x]);
}
int main()
{
	n=read();scanf("%s",ch+1);
	last=size=root=1;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=n;i>=1;i--)ins(ch[i]-'a',i);
	for(int i=2;i<=size;i++)add(t[i].fa,i);
	for(int i=1;i<=size;i++)
	{
		cmn[i]=1e9+1;cmx[i]=-1e9-1;
		if(sz[i])mx[i]=mn[i]=w[i];
		else mn[i]=1e9+1,mx[i]=-1e9-1;
	}
	for(int i=1;i<=n;i++)tr[i]=inf;
	dfs(1);
	for(int i=n-1;i>=0;i--)ans[i]=ans[i+1]+num[i];
	for(int i=0;i<n;i++)
	{
		tmp=query(n-i);
		printf("%lld %lld\n",ans[i],tmp==inf?0:tmp);
	}
	return 0;
}