「NOI 2015」品酒大会

题目链接:UOJ 131

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

在大会的晚餐上,调酒师 Rainbow 调制了 $n​$ 杯鸡尾酒。这 $n​$ 杯鸡尾酒排成一行,其中第 $i​$ 杯酒 ($1 \le i \le 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​$ 相似」、$\dots​$、「$(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, \dots, n − 1$,统计出有多少种方法可以选出两杯「$r$ 相似」的酒,并回答选择两杯「$r$ 相似」的酒调兑可以得到的美味度的最大值。

数据范围:$1 \le n \le 3 \times 10 ^ 5$,$\lvert a_i \rvert \le 10 ^ 9$。


Solution

题目中已经说明了本题的关键:

两杯「$r$ 相似」($r > 1$)的酒同时也是「$1$ 相似」、「$2$ 相似」、$\dots$、「$(r − 1)​$ 相似」的。

这启发我们从大到小枚举相似度,然后用并查集合并。具体实现为:先建立后缀数组,将所有后缀按照 $height$ 从大到小排序,维护每个集合内的最大值、最小值和答案。对于第一问,我们对每种相似度的答案做后缀和;对于第二问,我们对每种相似度的答案做后缀 $\max​$。

时间复杂度:$\mathcal O(n \log n)​$。


Code

#include <cstdio>
#include <algorithm>

const int N = 3e5 + 5;
const long long INF = 0x7f7f7f7f7f7f7f7f;

int n, a[N], fa[N], siz[N], id[N], mx[N], mn[N];
long long ret[N], ans1[N], ans2[N];
char s[N];

template <int MAX>
struct SuffixArray {
    static const int N = MAX;
    int n, m, sa[N], rk[N], cnt[N], tmp[N], height[N];
    void radixSort() {
        std::fill(cnt + 1, cnt + m + 1, 0);
        for (int i = 1; i <= n; i++) cnt[rk[i]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
    }
    template <typename Tp>
    void build(Tp *a, int _n, int _m) {
        n = _n, m = _m;
        for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
        radixSort();
        for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
            p = 0;
            for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
            radixSort();
            std::swap(rk, tmp);
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++) {
                int u = sa[i - 1], v = sa[i];
                int uu = (u + l <= n ? u + l : 0), vv = (v + l <= n ? v + l : 0);
                rk[sa[i]] = (tmp[u] == tmp[v] && tmp[uu] == tmp[vv] ? p : ++p);
            }
        }
        a[n + 1] = 0;
        for (int i = 1, k = 0; i <= n; i++) {
            k -= (k > 0);
            int j = sa[rk[i] - 1];
            for (; a[i + k] == a[j + k]; k++);
            height[rk[i]] = k;
        }
    }
};

SuffixArray<N> S;

template <typename Tp>
void cmax(Tp &x, Tp y) {
    x < y && (x = y);
}
template <typename Tp>
void cmin(Tp &x, Tp y) {
    x > y && (x = y);
}
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y, int len) {
    fa[y = find(y)] = x = find(x);
    ans1[len] += 1LL * siz[x] * siz[y];
    siz[x] += siz[y];
    cmax(ret[x], ret[y]);
    cmax(ret[x], std::max(1LL * mx[x] * mx[y], 1LL * mn[x] * mn[y]));
    cmax(ret[x], std::max(1LL * mx[x] * mn[y], 1LL * mn[x] * mx[y]));
    cmax(mx[x], mx[y]);
    cmin(mn[x], mn[y]);
    cmax(ans2[len], ret[x]);
}
int main() {
    scanf("%d%s", &n, s + 1);
    S.build(s, n, 255);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        fa[i] = id[i] = i, siz[i] = 1;
        mx[i] = mn[i] = a[i], ret[i] = -INF;
    }
    std::fill(ans2, ans2 + n, -INF);
    std::sort(id + 2, id + n + 1, [](int x, int y) {
        return S.height[x] > S.height[y];
    });
    for (int i = 2; i <= n; i++) {
        merge(S.sa[id[i]], S.sa[id[i] - 1], S.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] ? ans2[i] : 0LL);
    }
    return 0;
}

发表评论