洛谷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;
}