BZOJ 4199 - [Noi2015]品酒大会

#并查集 #后缀数组

Published on 2016-05-13

描述

UOJ 传送门：【NOI2015】品酒大会

分析

对于前面的部分分，很容易想到一个 $O(n^2)$ 的算法，即利用后缀数组求解 LCP，再暴力枚举两个后缀来更新答案。不难发现，两个 $r$ 相似的后缀 $i, j$ 同时也是 $0, 1, 2,...,r - 1$ 相似的。所以如果 LCP 的长度是 $r$ ，那么长度为 $0, 1, 2,...,r - 1$ 的答案也至少是 $a_ia_j$ ，所以我们只更新 $\mathrm{ans}(r)$ ，最后从大到小扫描一遍数组即可得到答案。
期望得分：50分。

再看满分的算法，上面的算法瓶颈在于需要暴力枚举后缀，能不能不暴力枚举后缀呢？
我们发现这样一个性质，如果一个集合 $s_x$ 里面的后缀两两 $x$ 相似，集合 $s_y$ 里面的后缀两两 $y$ 相似，如果有 $\mathrm{LCP}(\mathrm{Suffix}(i), \mathrm{Suffix}(j)) = p, i \in s_x, j \in s_y, p < x, p < y$ ，那么 $s_x \cup s_y = s$ 是两两 $y$ 相似的。

这启发我们从大的相似到小的相似做，然后在合并集合的时候更新答案。幸运的是，我们可以利用后缀数组实现这一点。

我们记录数组从大到小的下标位置（可用外排序实现，即 $i < j$ 当且仅当 $a_i < a_j$ ），然后依照从大到小的顺序遍历。对每个元素维护一个并查集，并查集的每个联通块记录元素数量，最大值，最小值（负数成负数有可能取到最大值）。

再令 $\mathrm{ans}(i)$ 记录所有恰好 $i$ 相似的元素对的最大乘积， $\mathrm{cnt}(i)$ 记录所有恰好 $i$ 相似的元素对的个数，这样对于每个，若其代表后缀 $\mathrm{Suffix}(i)$ 与 $\mathrm{Suffix}(j)$ 的最长公共前缀为 $r$ ，那么我们就可以合并 $i$ 和 $j$ 所在的集合，在合并的过程中，需要更新联通块的信息，也要利用乘法原理更新 $\mathrm{cnt}(r)$ ，运用两个联通块的最小最大值更新 $\mathrm{ans}(r)$ 。

下面来证明在从大到小遍历的过程中，一旦遍历完所有的，任意互为 $x, x \ge r$ 相似的元素对在同一个集合，也就是证明，上面的做法，不重复，不遗漏的统计了信息。

设最大的为 $m$ ，遍历完所有的以后，显然满足条件。
若对 $r + 1$ 成立，那么假设遍历到的 $\mathrm{height} = r$ ，代表后缀 $\mathrm{Suffix}(i)$ 与 $\mathrm{Suffix}(j)$ $r$ 相似。那么 $\mathrm{Suffix}(i)$ 与 $\mathrm{Suffix}(j)$ 不是 $r + 1$ 相似的，所以它们不在一个集合。
而所有与 $\mathrm{Suffix}(i)$ $x, x > r$ 相似的后缀已经跟 $i$ 在一个集合了，所有与 $\mathrm{Suffix}(j)$ $x, x > r$ 相似的后缀已经跟 $j$ ，并起来，新的集合互为 $r$ 相似，显然这一信息已被充分利用。

而所有 $\mathrm{height}[i] = r$ 被充分利用以后，结论自然被证明。

代码

//  Created by Sengxian on 5/13/16.
//  Copyright (c) 2016年 Sengxian. ALL rights reserved.
//  BZOJ 4198 NOI 2015 D1T2 后缀数组 + 并查集
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 300000 + 3;
char str[maxn];
int n, w[maxn];

namespace unionset {
    static const int maxNode = maxn;
    int fa[maxNode], maxV[maxNode], minV[maxNode], s[maxNode];
    inline void init(int n, int *val) {
        for (int i = 0; i < n; ++i) fa[i] = i, maxV[i] = minV[i] = val[i], s[i] = 1;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline ll unite(int x, int y, ll &ans) {
        x = find(x), y = find(y);
        if (x == y) return 0; //相同的集合不能合并！
        ans = max(ans, (ll)maxV[y] * maxV[x]);
        ans = max(ans, (ll)minV[y] * minV[x]);
        maxV[y] = max(maxV[y], maxV[x]);
        minV[y] = min(minV[y], minV[x]);
        ll res = (ll)s[x] * s[y];
        s[y] += s[x];
        fa[x] = y;
        return res;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

using namespace unionset;

namespace SA {
    static const int maxNode = maxn;
    int sa[maxNode], rank[maxNode], height[maxNode], n;
    char str[maxNode];
    void buildSA(int m) {
        static int cnt[maxNode], tmpSA[maxNode], rank1[maxNode], rank2[maxNode];
        n = strlen(str) + 1; str[n] = 0;
        fill(cnt, cnt + m, 0);
        for (int i = 0; i < n; ++i) cnt[(int)str[i]]++;
        for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; ++i) rank[i] = cnt[(int)str[i]] - 1;
        for (int l = 1; l < n; l <<= 1) {
            for (int i = 0; i < n; ++i)
                rank1[i] = rank[i], rank2[i] = i + l < n ? rank[i + l] : 0;
            fill(cnt, cnt + n, 0);
            for (int i = 0; i < n; ++i) cnt[rank2[i]]++;
            for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; --i) tmpSA[--cnt[rank2[i]]] = i;
            fill(cnt, cnt + n, 0);
            for (int i = 0; i < n; ++i) cnt[rank1[i]]++;
            for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; --i) sa[--cnt[rank1[tmpSA[i]]]] = tmpSA[i];
            bool unique = true;
            rank[sa[0]] = 0;
            for (int i = 1; i < n; ++i) {
                rank[sa[i]] = rank[sa[i - 1]];
                if (rank1[sa[i]] == rank1[sa[i - 1]] && rank2[sa[i]] == rank2[sa[i - 1]]) unique = false;
                else rank[sa[i]]++;
            }
            if (unique) break;
        }
    }
    void getHeight() {
        int k = 0;
        height[0] = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (k) --k;
            int j = sa[rank[i] - 1];
            while (str[i + k] == str[j + k]) k++;
            height[rank[i]] = k;
        }
    }
}

ll ans[maxn], cnt[maxn];
int order[maxn];

inline bool cmp(const int x, const int y) {
    return SA::height[x] > SA::height[y];
}

void solve() {
    fill(ans + 1, ans + n, -INF), fill(cnt + 1, cnt + n, 0);
    for (int i = 0; i < n - 1; ++i)
        cnt[SA::height[order[i]]] += unite(SA::sa[order[i]], SA::sa[order[i] - 1], ans[SA::height[order[i]]]);
    for (int i = n - 2; i; --i) ans[i] = max(ans[i], ans[i + 1]), cnt[i] += cnt[i + 1];
    printf("%lld %lld\n", (ll)n * (n - 1) / 2, ans[0]);
    for (int i = 1; i < n; ++i)
        if (cnt[i]) printf("%lld %lld\n", cnt[i], ans[i]);
        else puts("0 0");
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    if (n == 1) return puts("0 0"), 0;
    scanf("%s", SA::str);
    int mn1 = INT_MAX, mn2 = INT_MAX, mx1 = INT_MIN, mx2 = INT_MIN;
    for (int i = 0; i < n; ++i) {
        w[i] = ReadInt();
        int v = w[i];
        if (v < mn1) swap(mn1, v);
        if (v < mn2) swap(mn2, v);
        v = w[i];
        if (v > mx1) swap(mx1, v);
        if (v > mx2) swap(mx2, v);
    }
    ans[0] = max((ll)mn1 * mn2, (ll)mx1 * mx2);
    SA::buildSA('z' + 3);
    SA::getHeight();
    for (int i = 1; i < n; ++i) order[i] = i + 1; //注意结尾添加的字符
    sort(order, order + n, cmp);
    init(n, w);
    solve();
    return 0;
}

BZOJ 4200 - [Noi2015]小园丁与老司机后缀数组 - Suffix Array 防忘笔记

Sengxian's Blog

BZOJ 4199 - [Noi2015]品酒大会

描述

分析

代码