洛谷P2178 [NOI2015] 品酒大会题解

题目链接：P2178 [NOI2015] 品酒大会

题意：

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

在大会的晚餐上，调酒师 Rainbow 调制了 $n$ 杯鸡尾酒。这 $n$ 杯鸡尾酒排成一行，其中第 $n$ 杯酒 ($1 ≤ i ≤ n$) 被贴上了一个标签 $s_i$ ，每个标签都是 $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 > 1)$ 的酒同时也是 “ $1$ 相似”、“ $2$ 相似”、……、“ $(r - 1)$ 相似” 的。特别地，对于任意的 $1 \le p ,q \le n,p \ne q$，第 $p$ 杯酒和第 $q$ 杯酒都是“ $0$ 相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 $i$ 杯酒 ($1 ≤ i ≤ n$) 的美味度为 $a_i$ 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 $p$ 杯酒与第 $q$ 杯酒调兑在一起，将得到一杯美味度为 $a_p\times a_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$ 。

数据范围：

$1 \le n \le 3\times 10^5,~0\le |a_i| \le 10^9$

首先两个串最多 $r$ 相似等价于后缀 $\operatorname{suf} i$ 和 $\operatorname{suf} j$ 的最长公共前缀 (LCP) 的长度等于 $r$ 。

套路地对字符串建立后缀数组，这样问题就转化为有多少个点对 $(i,j)$ 满足

$\min_{i+1 \le k \le j} \{\operatorname{height} k\} = x\quad(x=0,1,\cdots,r-1)$

这下好了，好像单调队列单调栈都不好算这个东西。（~~怎么后缀数组就这么一个 height 能有这么多花样？~~）

考虑倒序枚举 $x$ 并用 vector 维护每个 height 值是 $x$ 的位置。

然后创建一个新的空数组，依次插入这些位置，对于位置 $i$ 计算贡献后合并两侧已经出现的集合。

举个例子，目前考虑到 $x=3$ 的位置 $i=3$ ，数组为 $5\,4\,\texttt{}\,4\,5\,6\,7\,\texttt{}\,\texttt{*}\, 8$ ，那么合并左右的 54 和 4567。

设它左右的集合为 $S,T$ （没有则为空集 $\varnothing$），那么 $i$ 产生的贡献为

$(|S|+1)(|T| + 1) - 1$

这里 $+1$ 是因为 $i$ 自己可以作为后缀， $-1$ 是去掉 $i$ 和自己配对的情况。

考虑并查集维护集合的合并操作。这样第二问也随之解决了，即我们维护集合的最大值最小值即可。

这里维护最小值是因为题目中的 $a_i$ 会有负数，然后负负得正可能比最大值乘最大值大，很坑。

实现的时候每次直接将 $i$ 和 $i-1$ 合并，并计算 $i$ 所在集合大小乘以 $i-1$ 所在集合大小即可。

时间复杂度 $\mathcal{O}(n \log n)$ 或 $\mathcal{O}(n)$ ，取决于构建后缀数组的复杂度。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))
#define chk(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N]; vector<int> vec[N];
struct node { int fa, sz, mn, mx; } tr[N];
int n, res, num = -INF, a[N], ans1[N], ans2[N];
int cnt[N], sa[N], rk[N * 2], tmp[N * 2], height[N];
void sort(const int m, int w)
{
    memset(cnt, 0, (m + 5) * sizeof(int));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getsa()
{
    const int m = max(n, 233ll);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(m, w); sort(m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(chk(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
void getheight()
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
int find(int x) { return tr[x].fa == x ? x : tr[x].fa = find(tr[x].fa); }
void merge(int u, int v)
{
    int x = find(u), y = find(v); if(tr[x].sz > tr[y].sz) swap(x, y);
    res += tr[x].sz * tr[y].sz; up(num, max(tr[x].mx * tr[y].mx, tr[x].mn * tr[y].mn));
    tr[x].fa = y; tr[y].sz += tr[x].sz; up(tr[y].mx, tr[x].mx); down(tr[y].mn, tr[x].mn);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s + 1); getsa(); getheight();
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        tr[i] = {i, 1, a[sa[i]], a[sa[i]]};
        vec[height[i]].push_back(i);
    }
    for(int i = n - 1; ~i; i--)
    {
        for(int j : vec[i]) if(j > 1) merge(j - 1, j);
        if(res > 0) { ans1[i] = res, ans2[i] = num; }
    }
    for(int i = 0; i < n; i++) cout << ans1[i] << ' ' << ans2[i] << '\n';
    return 0;
}