P2178 [NOI2015]品酒大会

发表于 | 阅读数

$∀i∈[0,n)$求有多少对后缀满足$Len(lcp)\ge i$,以及满足条件的两个后缀的权值乘积的最大值

考虑从小到大递增增加。

后缀数组里，如果$Len(lcp)\ge x$，会把$he[i]\geq x$都包含进来。即对数就是各个集合的$\sum C_{size}^2$，最大就是每个集合中最大$\times$此大。

显然随着$x$，减小越来越多$he[i]$，会连接集合，用并茶集维护即可。

  • 不用维护最大次小，只需要在合并的时候$mx[x]\times mx[y]$即可。
  • 考虑负值维护最大值和最小值即可。
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e6 + 10;
const int mod = 1e9 + 7;

struct SA
{
    int ra[N], y[N], sa[N];
    int tn[N], he[N];
    int tmp[N];
    void GetSA(char *t, int siz)
    {
        int len = strlen(t + 1);
        for (int i = 0; i <= siz; i++)
            tn[i] = 0;
        for (int i = 1; i <= len; i++)
            ra[i] = t[i], tn[ra[i]]++;
        for (int i = 1; i <= siz; i++)
            tn[i] += tn[i - 1];
        for (int i = len; i >= 1; i--)
            sa[tn[ra[i]]--] = i;
        for (int k = 1; k <= len; k <<= 1)
        {
            int cnt = 0;
            for (int i = len - k + 1; i <= len; i++)
                y[++cnt] = i;
            for (int i = 1; i <= len; i++)
                if (sa[i] > k)
                    y[++cnt] = sa[i] - k;
            for (int i = 0; i <= siz; i++)
                tn[i] = 0;
            for (int i = 1; i <= len; i++)
                tn[ra[i]]++;
            for (int i = 1; i <= siz; i++)
                tn[i] += tn[i - 1];
            for (int i = len; i >= 1; i--)
                sa[tn[ra[y[i]]]--] = y[i];
            for (int i = 1; i <= len; i++)
                tmp[i] = ra[i];
            cnt = 1;
            ra[sa[1]] = 1;
            for (int i = 2; i <= len; i++)
                ra[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k]) ? cnt : ++cnt;
            if (cnt == len)
                break;
            siz = cnt;
        }
        for (int i = 1; i <= len; ++i)
            ra[sa[i]] = i;
        for (int i = 1, j = 0; i <= len; ++i)
        {
            if (j)
                --j;
            while (t[i + j] == t[sa[ra[i] - 1] + j])
                ++j;
            he[ra[i]] = j;
        }
        he[1] = 0;
    }
} T;
int fa[N];
int siz[N], fm[N], zm[N];
int a[N];
ll mx[N];
ll maxx[N];
ll f[N];
int find(int x)
{
    if (fa[x] != x)
        return fa[x] = find(fa[x]);
    return x;
}
void Union(int x, int y, int id)
{

    int xx = find(x);
    int yy = find(y);
    f[id] += 1ll * siz[xx] * siz[yy];
    fa[yy] = xx;

    mx[xx] = max(mx[xx], mx[yy]);
    ll p = max(1ll * fm[xx] * fm[yy], max(max(1ll * fm[xx] * zm[yy], 1ll * fm[yy] * zm[xx]), 1ll * zm[xx] * zm[yy]));

    mx[xx] = max(p, mx[xx]);
    fm[xx] = min(fm[xx], fm[yy]);
    zm[xx] = max(zm[xx], zm[yy]);

    maxx[id] = max(maxx[id], mx[xx]);

    siz[xx] += siz[yy];
}
char s[N];
vector<pii> p;

int main()
{
    int len;
    scanf("%d", &len);
    scanf("%s", s + 1);

    T.GetSA(s, 122);
    for (int i = 1; i <= len; i++)
        scanf("%d", &a[i]);
    for (int i = 2; i <= len; i++)
        p.push_back(mk(T.he[i], i));
    for (int i = 1; i <= len; i++)
        fa[i] = i, siz[i] = 1, zm[i] = fm[i] = a[i], mx[i] = -2e18;
    sort(p.begin(), p.end(), greater<pii>());

    int cnt = 0;
    maxx[len + 1] = -2e18;
    for (int i = len; i >= 0; i--)
    {
        maxx[i] = -2e18;
        while (cnt < p.size() && p[cnt].first >= i)
            Union(T.sa[p[cnt].second - 1], T.sa[p[cnt].second], i), cnt++;
        f[i] += f[i + 1];
        maxx[i] = max(maxx[i], maxx[i + 1]);
    }
    for (int i = 0; i < len; i++)
    {
        printf("%lld %lld\n", f[i], maxx[i] == -2e18 ? 0 : maxx[i]);
    }
}