NOI2015 品酒大会

发表于 | 分类于

NOI2015 品酒大会

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

在大会的晚餐上，调酒师 Rainbow 调制了$ n $杯鸡尾酒。这$ n $杯鸡尾酒排成一行，其中第 $i$ 杯酒 $（1≤i≤n）$ 被贴上了一个标签$ si$，每个标签都是 $26$ 个小写英文字母之一。设 $Str(l,r)$ 表示第 $l$ 杯酒到第$ r$ 杯酒的$ r−l+1$ 个标签顺次连接构成的字符串。若 $Str(p,po)=Str(q,qo)$，其中 $1≤p≤po≤n，p≠q，po−p+1=qo−q+1=r$，则称第$ p$ 杯酒与第$ q $杯酒是“$r$相似” 的。当然两杯“$r$相似” $（r>1）$的酒同时也是“1 相似”、“2 相似”、……、“$(r−1)$相似”的。特别地，对于任意的 $1≤p,q≤n，p≠q$，第$ p $杯酒和第$ q $杯酒都是“0相似”的。

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

输入格式
输入文件的第 1 行包含 1 个正整数 $n$，表示鸡尾酒的杯数。

第 2 行包含一个长度为 $n$ 的字符串 S，其中第 $i$ 个字符表示第 $i$ 杯酒的标签。

第 3 行包含 $n$ 个整数，相邻整数之间用单个空格隔开，其中第 $i$ 个整数表示第 $i$ 杯酒的美味度 $a_i$。

输出格式
输出文件包括 $n $行。第 $i $行输出 2 个整数，中间用单个空格隔开。第 1 个整数表示选出两杯“$(i−1)$相似”的酒的方案数，第 2 个整数表示选出两杯“$(i−1)$相似”的酒调兑可以得到的最大美味度。若不存在两杯“$(i−1)$相似”的酒，这两个数均为 0。

样例一
input

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7

output

45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0

样例二
input

12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

output

66 120
34 120
15 55
12 40
9 27
7 16
5 7
3 -4
2 -4
1 -4
0 0
0 0

题解

其实$r$相似就是LCP>$r$，所以考虑子串LCP问题采用后缀数组来进行解决。如果暴力枚举子串是$n^2$的，复杂度难以接受，考虑可以将height进行排序然后利用求LCP时对height取min这个操作来进行优化。

假设当前我处理到height值为h的拍完顺序的子串，那么显然答案由所有height值为h的子串贡献而来，我们需要把所有height值为h的子串合并到一起进行计算。但是一些height值大于当前h的也算作h相似，考虑我当前插入的子串$S’$，跟之前所有的height值处理过>=h的一起考虑LCP，都是=h的，所以我们采用并查集维护拍过序之后的后缀，每次合并两个已经处理的集合，然后更新答案即可。注意要记录一下最大值和最小值，因为$a_i$可能为-,但是负数相乘得到的整数可能作为答案，所以只需要维护集合大小，最大值，最小值即可。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+1e3+7;
const ll INF=(ll)(1ll<<62);
int wa[N],wb[N],wv[N],tong[N],rank[N],sa[N],height[N];
int n;
char s[N];
ll a[N],fa[N],size[N],mx[N],mn[N];
ll ans[2][N];
struct node{
	int h,l,r;
}v[N];
bool cmp(int *r,int a,int b,int l)
{
	return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<n;i++)
		tong[x[i]=r[i]]++;
	for(i=1;i<m;i++)
		tong[i]+=tong[i-1];
	for(i=n-1;i>=0;i--)
		sa[--tong[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++)
			y[p++]=i;
		for(i=0;i<n;i++)
			if(sa[i]>=j)
				y[p++]=sa[i]-j;
		for(i=0;i<=m;i++)
			tong[i]=0;
		for(i=0;i<n;i++)
			tong[wv[i]=x[y[i]]]++;
		for(i=1;i<m;i++)
			tong[i]+=tong[i-1];
		for(i=n-1;i>=0;i--)
			sa[--tong[wv[i]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight(char *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++)
		rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)
		for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
bool operator <(node a,node b)
{
	return a.h>b.h;
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	da(s,sa,n+1,129);
	calheight(s,sa,n);
	for(int i=1;i<=n;i++)
	{
		ans[1][i]=-INF;
		mx[rank[i-1]]=mn[rank[i-1]]=a[i];
		fa[i]=i;
		size[i]=1;
	}
	for(int i=2;i<=n;i++)
		v[i].h=height[i],v[i].l=i-1,v[i].r=i;
	sort(v+2,v+n+1);
	int now=2;
	for(int i=n-1;i>=0;i--)
	{
		ans[0][i]=ans[0][i+1];
		ans[1][i]=ans[1][i+1];
		while(now<=n&&v[now].h==i)
		{
			int x=find(v[now].l),y=find(v[now].r);
			ans[0][i]+=size[x]*size[y];
			ans[1][i]=max(ans[1][i],mx[x]*mx[y]);
			ans[1][i]=max(ans[1][i],mn[x]*mn[y]);
			if(x!=y)
			{
				fa[y]=x;
				size[x]+=size[y];
				mx[x]=max(mx[x],mx[y]);
				mn[x]=min(mn[x],mn[y]);
			}
			now++;
		}
	}
	for(int i=0;i<=n-1;i++)
		printf("%lld %lld\n",ans[0][i],(ans[1][i]==-INF?0:ans[1][i]));
}