【题解】[Noi2015] 品酒大会 后缀数组 BZOJ – 4199

题目链接_(:зゝ∠)_

似乎还是比较简单的

首先用后缀数组求出 $Height$数组

由于两个后缀的 $lcp$是 $Height$的一段连续区间最小值，因此如果区间中有某处 $Height$值 $< k$，那么它就会把区间分成两段，左边一段和右边一段之间是不能构成 $k$相似的

也就是说我们只要计算连续的一段 $Height \geq k$的块的贡献就行了

当 $k$由大变小时，块与块之间会逐渐变得联通，两个答案都是递增的，用并查集维护一下块大小、最大值、次大值、最小值、次小值就行了

其实我觉得出题人搞出负数来就很没有意义，纯粹浪费选手时间了，但是样例给的还是很良心的，所以就不吐槽啦 OvO

复杂度 $O(n \log _ 2 n)$

（如果后缀数组写 $O(n)$的那复杂度就在并查集了，$O(\alpha n)$）

代码：

#include <bits/stdc++.h>

#define NS (600005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, A[NS];

char str[NS];

struct suffixArray
{
    int n, SA[NS], x[NS], y[NS], T[NS], H[NS];
    char s[NS];
    void RSort(int p)
    {
        memset(T + 1, 0, sizeof(int) * p);
        for (int i = 1; i <= n; i += 1) T[x[y[i]]]++;
        for (int i = 1; i <= p; i += 1) T[i] += T[i - 1];
        for (int i = n; i >= 1; i -= 1) SA[T[x[y[i]]]--] = y[i];
    }
    #define cmp(a, b) (y[a] == y[b] && y[(a) + l] == y[(b) + l])
    void run(char (&S)[NS])
    {
        memmove(s, S, sizeof(s)), n = strlen(s + 1);
        memset(x, 0, sizeof(x)), memset(y, 0, sizeof(y));
        for (int i = 1; i <= n; i += 1) x[i] = s[i] - 'a' + 1, y[i] = i;
        int p = 26; RSort(p);
        for (int l = 1, q = 0; q < n; l <<= 1, p = q)
        {
            q = 0;
            for (int i = n - l + 1; i <= n; i += 1) y[++q] = i;
            for (int i = 1; i <= n; i += 1)
                if (SA[i] > l) y[++q] = SA[i] - l;
            RSort(q), swap(x, y), q = x[SA[1]] = 1;
            for (int i = 2; i <= n; i += 1)
                if (cmp(SA[i], SA[i - 1])) x[SA[i]] = q;
                else x[SA[i]] = ++q;
        }
        for (int i = 1, j, lcp = 0; i <= n; i += 1)
        {
            if (lcp) lcp--;
            j = SA[x[i] - 1];
            while (s[i + lcp] == s[j + lcp]) lcp++;
            H[x[i]] = lcp;
        }
    }
    #undef cmp
} sa;

vector<int> l[NS];

int f[NS], fp[NS], sp[NS], fn[NS], sn[NS], sz[NS];

LL r1, r2 = LLONG_MIN, a1[NS], a2[NS];

int findf(int a) { return f[a] == a ? a : f[a] = findf(f[a]); }

LL cal(int a)
{
    LL res = LLONG_MIN;
    if (fp[a] != INT_MIN && fn[a] != INT_MAX) res = 1ll * fp[a] * fn[a];
    if (sp[a] != INT_MIN) res = max(res, 1ll * fp[a] * sp[a]);
    if (sn[a] != INT_MAX) res = max(res, 1ll * fn[a] * sn[a]);
    return res;
}

void merge(int a, int b)
{
    a = findf(a), b = findf(b);
    if (a == b) return;
    r1 -= 1ll * sz[a] * (sz[a] - 1) / 2;
    r1 -= 1ll * sz[b] * (sz[b] - 1) / 2;
    f[b] = a, sz[a] += sz[b];
    if (fp[b] > fp[a]) sp[a] = max(fp[a], sp[b]), fp[a] = fp[b];
    else sp[a] = max(sp[a], fp[b]);
    if (fn[b] < fn[a]) sn[a] = min(fn[a], sn[b]), fn[a] = fn[b];
    else sn[a] = min(sn[a], fn[b]);
    r1 += 1ll * sz[a] * (sz[a] - 1) / 2, r2 = max(r2, cal(a));
}

int main(int argc, char const* argv[])
{
    IN(n), scanf("%s", str + 1), sa.run(str);
    for (int i = 2; i <= n; i += 1) l[sa.H[i]].push_back(i);
    for (int i = 1; i <= n; i += 1)
    {
        IN(A[i]), f[i] = i, sp[i] = INT_MIN, sn[i] = INT_MAX, sz[i] = 1;
        if (A[i] >= 0) fp[i] = A[i], fn[i] = INT_MAX;
        else fn[i] = A[i], fp[i] = INT_MIN;
    }
    for (int i = n - 1; i >= 0; i -= 1)
    {
        for (int j = 0; j < l[i].size(); j += 1)
            merge(sa.SA[l[i][j] - 1], sa.SA[l[i][j]]);
        a1[i] = r1, a2[i] = r2;
    }
    for (int i = 0; i < n; i += 1)
        printf("%lld %lld\n", a1[i], a2[i] == LLONG_MIN ? 0 : a2[i]);
    return 0;
}