「Bzoj 4199」「NOI2015」品酒大会 (后缀数组+并查集)

BZOJ 4199
题意:见上。

40分即枚举两个点Hash即可。
50分改为枚举长度+一个点,Hash即可。
考虑100分情况
我们发现两个答案都是都是递减的,所以我们可以逆向求答案。(后缀和过程)
这题显然是要用后缀数组了
我们将$height$值一样的存在一个vector里,然后按照$height$值倒着求答案。
附上样例一说明,SA后我们会得到如下的信息:

i    height    sa    stringsai asai
1    0        10    i          7
2    1        5    iiipoi      4
3    2        6    iipoi      8
4    1        7    ipoi      3
5    0        3    noiiipoi  4
6    0        9    oi          4
7    2        4    oiiipoi      7
8    1        2    onoiiipoi 1
9    0        8    poi          6
10    2        1    ponoiiipoi2

具体可以看xht 37 大佬的题解
这里直接讲并查集做法,即每次找一个位置,就把他和$SA$序上$i-1$位和$i$位的位置在并查集上合并,那么下次找的话,就可以直接统计两个连通块的信息。
并查集维护集合大小,集合最大值最小值(有负数存在,所以最大乘积可能来自最小值),以上从上面的表格中可以分析出来

知识点

1、注意不要将SA的任何字符映射到0

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 300000 + 5;
    const LL INF = 1e18 + 2;

    char ch[MAXN];
    int a[MAXN], n, m, v[MAXN];
    int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];

    void build() {//构造后缀数组 
        for (int i = 1; i <= m; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
        for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
        for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//基数排序排第一轮

        for (int k = 1; k <= n; k <<= 1) {
            int p = 0;
            for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)无第二关键字,所以排序应该排在前面
            for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
            //只有SA[i]>=k的SA[i]才是第二关键字的位置 
            //从图中可以看出第一关键字和第二关键字的位置相差k,故SA[i] - k 
            for (int i = 1; i <= m; ++i) tax[i] = 0;
            for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名 
            for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
            for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//保证了第一关键字的顺序再排第二关键字 
            //基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标) 
            swap(rk, tp);//此时tp没用,暂存上一轮rank的值
            p = 1, rk[SA[1]] = 1;
            for (int i = 2; i <= n; ++i) 
                rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
            //算排名第i的数的rank,按sa顺序能够保证rank的正确性,但是要cmp判断与上一个字符串相等的情况 
            if (p >= n) break;//剪枝,已经没有重复元素 
            m = p; 
        }
        int k = 0;//k是比i-1前一名的后缀
        for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...的顺序计算 
            if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
            int j = SA[rk[i] - 1]; //前一名的后缀位置 
            while (ch[i + k] == ch[j + k]) k++; //往后比较 
            height[rk[i]] = k;  //更新答案 
        }
    }

    int f[MAXN], maxd[MAXN], mind[MAXN], sz[MAXN];
    LL mp[MAXN], ans1, ans2, fans[MAXN][2];
    vector<int > vec[MAXN];

    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    void merge(int x, int y) {
        if (sz[x] > sz[y]) swap(x, y);
        f[x] = y;
        ans1 += 1ll * sz[x] * sz[y];
        sz[y] += sz[x];
        mp[y] = max(mp[y], max(1ll * maxd[x] * maxd[y], 1ll * mind[x] * mind[y]));
        maxd[y] = max(maxd[x], maxd[y]);
        mind[y] = min(mind[x], mind[y]);
        ans2 = max(ans2, mp[y]);
    }

    void clean() {
        ms(fans, 0), m = 30;
    }
    int solve() {

        clean();
        cin >> n;
        scanf("%s", ch + 1);
        for (int i = 1; i <= n; ++i) scanf("%d", &v[i]), a[i] = ch[i] - 'a' + 1;
        build();
        for (int i = 1; i <= n; ++i) {
            f[i] = i, sz[i] = 1;
            maxd[i] = mind[i] = v[SA[i]];
            mp[i] = -INF;
        }
        ans1 = 0, ans2 = -INF;
        for (int i = 1; i <= n; ++i) vec[height[i]].push_back(i);

        for (int len = n - 1; len >= 0; --len) {
            for (int i = 0; i < (int)vec[len].size(); ++i) {
                int u = vec[len][i];
                merge(find(u), find(u - 1));
                if (ans1)
                    fans[len][0] = ans1, fans[len][1] = ans2;
            }
        }

        for (int i = 0; i < n; ++i) printf("%lld %lld\n", fans[i][0], fans[i][1]);

        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}
/*
4
aaaa
1 1 1 1
*/

------ 本文结束 ------