NOI2015 品酒大会

发表于 | 更新于 | 分类于 | 阅读次数：

[NOI2015] 品酒大会

Description

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

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

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

对于$100 %$的数据，满足$n \le 3 \times 10^5,\ |a_i| \le 10 ^ 9$。

Solution

其实这题挺清新的，只是题目略长。我的做法是后缀数组+并查集

先看第一问。很容易想到根据 $r$ 从后往前做，最后扫一遍累加。

建出后缀数组，我们将 $\text{height}$ 从大到小排序，对于 $\text{height}$ 值为 $r$ 的后缀 $i$，它和排在它前面一名的后缀 $r$ 相似，并且在 $\text{SA}$ 数组中，与 $i$ 相邻且排在 $i$ 后面的后缀都能够和 $i$ 的前一名构成 $r$ 相似。这便是我们从后往前做的原因。因为排在 $i$ 后面、与 $i$ 相邻的后缀必然已经在之前统计过了。我们用并查集维护每一个后缀所在集合的大小，每次统计答案时，将 $i$ 和排在 $i$ 前一名后缀的集合合并，对答案的贡献就是 $\text{size}$ 值相乘。

第二问其实差不多，我们在并查集中多维护 $\max$ 和 $\min$（维护 $min$ 是因为有负数），合并时相乘更新即可。

时间复杂度$\mathcal {O} (n \log n)$

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long

namespace Suffix_Array {
	const int N = 3e5, LOG = 20;
	int n, S = 300, SA[N + 5], rank[N + 5], tp[N + 5], tax[N + 5], height[N + 5];
	int a[N + 5], fa[N + 5], size[N + 5], id[N + 5];
	LL ans1[N + 5], ans2[N + 5], Min[N + 5], Max[N + 5], Val[N + 5];
	char str[N + 5];
	inline void Init() {
		scanf("%d%s", &n, str + 1);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
			Max[i] = Min[i] = a[i], Val[i] = -2e18;
			fa[i] = id[i] = i, size[i] = 1;
		}
		memset(ans2, 0xcf, sizeof(ans2));
	}
	inline void Radix_Sort() {
		for (int i = 1; i <= S; ++i) tax[i] = 0;
		for (int i = 1; i <= n; ++i) tax[rank[i]]++;
		for (int i = 1; i <= S; ++i) tax[i] += tax[i - 1];
		for (int i = n; i >= 1; --i) SA[tax[rank[tp[i]]]--] = tp[i];
	}
	inline void Build() {
		for (int i = 1; i <= n; ++i) rank[i] = str[i] - 'a' + 1, tp[i] = i;
		Radix_Sort();
		for (int len = 1, p = 0; p < n; len <<= 1, S = p) {
			p = 0;
			for (int i = n - len + 1; i <= n; ++i) tp[++p] = i;
			for (int i = 1; i <= n; ++i) if (SA[i] > len) tp[++p] = SA[i] - len;
			Radix_Sort();
			std::swap(rank, tp);
			rank[SA[1]] = p = 1;
			for (int i = 2; i <= n; ++i) rank[SA[i]] = tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + len] == tp[SA[i - 1] + len] ? p : ++p;
		}
		for (int i = 1, H = 0; i <= n; ++i) {
			if (rank[i] == 1) continue;
			H -= (H > 0);
			for (int j = SA[rank[i] - 1]; str[i + H] == str[j + H]; ++H);
			height[rank[i]] = H;
		}
	}
	int Find(int x) {
		return fa[x] == x ? x : (fa[x] = Find(fa[x]));
	}
	inline void Merge(int x, int y, int len) {
		x = Find(x), y = Find(y);
		if (size[x] < size[y]) std::swap(x, y);
		ans1[len] += 1LL * size[x] * size[y];
		fa[y] = x, size[x] += size[y];
		Val[x] = std::max(Val[x], std::max(std::max(Max[x] * Max[y], Min[x] * Min[y]), std::max(Max[x] * Min[y], Min[x] * Max[y])));
		Max[x] = std::max(Max[x], Max[y]);
		Min[x] = std::min(Min[x], Min[y]);
		ans2[len] = std::max(ans2[len], Val[x]);
	}
	inline bool Cmp(const int &x, const int &y) {
		return height[x] > height[y];
	}
	inline void Solve() {
		std::sort(id + 2, id + 1 + n, Cmp);
		for (int i = 2; i <= n; ++i)
			Merge(SA[id[i]], SA[id[i] - 1], height[id[i]]);
		for (int i = n - 2; i >= 0; --i) {
			ans1[i] += ans1[i + 1];
			ans2[i] = std::max(ans2[i], ans2[i + 1]);
		}
		for (int i = 0; i < n; ++i) printf("%lld %lld\n", ans1[i], ans1[i] > 0 ? ans2[i] : 0);
	}
}
using namespace Suffix_Array;

int main() {
	Init();
	Build();
	Solve();
	return 0;
}