BZOJ3676【NOI2015】品酒大会 <后缀数组+并查集>

Problem

BZOJ3676【NOI2015】品酒大会

Time Limit: $10 Sec$
Memory Limit: $512 MB$

Description

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。
在大会的晚餐上，调酒师 $Rainbow$ 调制了 $n$ 杯鸡尾酒。这 $n$ 杯鸡尾酒排成一行，其中第 $i$ 杯酒 $(1\le i\le n)$ 被贴上了一个标签 $s_i$，每个标签都是 $26$ 个小写英文字母之一。设 $str(i,j)$ 表示第 $i$ 杯酒到第 $j$ 杯酒的 $j-i+1$ 个标签顺次连接构成的字符串。若 $str(l_1,r_1)=str(l_2,r_2)$，其中$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$，$l_1\ne l_2$，$r_1-l_1+1=r_2-l_2+1=p$，则称第 $l_1$ 杯酒与第 $l_2$ 杯酒是“$p$ 相似”的。当然两杯“$p$ 相似” $(p>1)$ 的酒同时也是“$1$ 相似”、“$2$ 相似”、……、“$(p-1)$ 相似”的。特别地，对于任意的$1\le p,q\le n, p\ne q$，第 $p$ 杯酒和第 $q$ 杯酒都是“$0$ 相似”的。
在品尝环节上，品酒师 $Freda$ 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 $i$ 杯酒$(1\le i\le n)$ 的美味度为 $a_i$。现在 $Rainbow$ 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 $i$ 杯酒与第 $j$ 杯酒调兑在一起，将得到一杯美味度为 $a_i\times a_j$ 的酒。现在请各位品酒师分别对于 $p = 0,1,2,\cdots ,p-1$，统计出有多少种方法可以选出 $2$ 杯“$p$ 相似”的酒，并回答选择 $2$ 杯“$p$相似”的酒调兑可以得到的美味度的最大值。

Input

第 $1$ 行包含 $1$ 个正整数 $n$，表示鸡尾酒的杯数。
第 $2$ 行包含一个长度为 $n$ 的字符串 $S$，其中第 i 个字符表示第 $i$ 杯酒的标签。
第 $3$ 行包含 $n$ 个整数，相邻整数之间用单个空格隔开，其中第 $i$ 个整数表示第 $i$ 杯酒的美味度 $a_i$。

Output

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

Sample

Sample 1

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

Explanation
二元组 $(p,q)$ 表示第 $p$ 杯酒与第 $q$ 杯酒。
$0$ 相似：所有 $45$ 对二元组都是 $0$ 相似的，美味度最大的是 $8\times 7=56$。
$1$ 相似：$(1,8)(2,4)(2,9)(4,9)(5,6)(5,7)(5,10)(6,7)(6,10)(7,10)，最大的是$$8\times 7=56$。
$2$ 相似：$(1,8)(4,9)(5,6)，最大的是 $4\times 8=32$。
没有 $3,4,5,\cdots ,9$ 相似的两杯酒，故均输出 $0$。

Sample 2

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

HINT

对于 $40\%$ 的数据， $n\le 2000$。
有 $10\%$ 的数据，不存在“$10$ 相似”的酒。
有 $20\%$ 的数据，所有 $a_i$ 的值都相等。
对于 $100\%$ 的数据， $1\le n\le 300000,\ |a_i|\le 10^9$。

标签：后缀数组 并查集

Solution

建后缀数组后统计每种$height$的后缀对有哪些，发现当从高向低枚举相似度$p$时，只会有越来越多的字符串满足，则每次合并新加进来的后缀对，用并查集维护。即若后缀$i$和$i-1$最高为$k$相似，则从$n$倒叙枚举到$k$时把$i$和$i-1$所在的集合合并。

Code

#include <bits/stdc++.h>
#define MAX_N 300000
using namespace std;
typedef long long lnt;
int n, a[MAX_N+5];    char s[MAX_N+5];
int sa[MAX_N+5], rk[MAX_N+5], height[MAX_N+5], tsa[MAX_N+5], cntA[MAX_N+5], cntB[MAX_N+5], A[MAX_N+5], B[MAX_N+5];
lnt ans[MAX_N+5][2];    vector <int> m[MAX_N+5];	int fa[MAX_N+5], mina[MAX_N+5], maxa[MAX_N+5], size[MAX_N+5];
int getf(int x) {return x == fa[x] ? x : fa[x] = getf(fa[x]);}
void CalcSA() {
    for (int i = 1; i <= 26; i++) cntA[i] = 0;
    for (int i = 1; i <= n; i++) cntA[s[i]-'a'+1]++;
    for (int i = 1; i <= 26; i++) cntA[i] += cntA[i-1];
    for (int i = n; i >= 1; i--) sa[cntA[s[i]-'a'+1]--] = i;	rk[sa[1]] = 1;
    for (int i = 2; i <= n; i++) {rk[sa[i]] = rk[sa[i-1]];	if (s[sa[i]] != s[sa[i-1]]) rk[sa[i]]++;}
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 1; i <= n; i++) cntA[i] = 0;	for (int i = 1; i <= n; i++) cntB[i] = 0;
        for (int i = 1; i <= n; i++) cntA[A[i] = rk[i]]++, cntB[B[i] = (i+l <= n) ? rk[i+l] : 0]++;
        for (int i = 1; i <= n; i++) cntB[i] += cntB[i-1];	for (int i = n; i >= 1; i--) tsa[cntB[B[i]]--] = i;
        for (int i = 1; i <= n; i++) cntA[i] += cntA[i-1];	for (int i = n; i >= 1; i--) sa[cntA[A[tsa[i]]]--] = tsa[i];
        rk[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            rk[sa[i]] = rk[sa[i-1]];
            if (A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) rk[sa[i]]++;
        }
    }
    for (int i = 1, j = 0; i <= n; i++) {
        if (j)	j--;
        while (s[i+j] == s[sa[rk[i]-1]+j]) j++;
        height[rk[i]] = j;
    }
}
int main() {
    scanf("%d", &n), scanf("%s", s+1);	lnt tot = 0, pro = 0;
    for (int i = 1; i <= n; i++) scanf("%d", a+i);	CalcSA();
    for (int i = 2; i <= n; i++) m[height[i]].push_back(i);
    for (int i = 1; i <= n; i++) fa[i] = i, size[i] = 1, mina[i] = maxa[i] = a[sa[i]];
    for (int i = n-1; ~i; i--) {
        for (int j = 0; j < (int)m[i].size(); j++) {
            int u = getf(m[i][j]), v = getf(m[i][j]-1);	if (u == v)	continue;
            if (!tot) pro = max(1LL*mina[u]*mina[v], 1LL*maxa[u]*maxa[v]);
            else pro = max(pro, max(1LL*mina[u]*mina[v], 1LL*maxa[u]*maxa[v]));
            tot += 1LL*size[u]*size[v], fa[v] = u, size[u] += size[v];
            mina[u] = min(mina[u], mina[v]), maxa[u] = max(maxa[u], maxa[v]);
        }
        ans[i][0] = tot, ans[i][1] = pro;
    }
    for (int i = 0; i < n; i++) printf("%lld %lld\n", ans[i][0], ans[i][1]);	return 0;
}