Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P2178 【[NOI2015]品酒大会】

posted on 2019-08-28 12:41:56 | under 题解 |

原题意:有多少个串的 $lcp(i, j) >= r$ (其中r为1~n中每一个数)

我们先不管第二问,只看第一问

第一次转化

首先不难发现一个非常好的性质:对于一个r相似的两杯酒,他们肯定也是r-1相似,r-2相似……

于是,我们考录倒序枚举,於是问题转化成了:有多少个串的 $lcp(i, j) == r$ (其中r为1~n中每一个数)

第二次转化

看到lcp,我们不难想到后缀数组, $lcp(i, j) == r$ 又等价于 $min(he[i + 1], he[i + 2], ……, he[j])$

于是我们把问题重新考虑,就转化成了:求出he数组,然后问有多少个数对,满足 $i - j$ 的he的最小值恰好等于r

第三次转化

我们把he数组降序排一遍序,然后按照顺序插入

然后我们可以把问题理解成:对于每次插入,我可以连接连续两堆数,然后这两堆数中每一个数值都比r大,所以我们可以把第一堆数的个数和第二堆数的个数相乘,得到的就是这两堆数对答案的贡献

举个例子:

假设我现在的数列长这样(还未被插入的数(即比r小的数)为*): $5\ 4\ *\ 4\ 5\ 6\ 7\ *\ *\ 4\ *\ 8$

然后我现在要在第三个位置插入一个3

不难发现,一共有 $(2 + 1) * (4 + 1) - 1 = 14$ 种方案(+1是因为3本身也可以算进来, -1是因为 $[3, 3]$ 不能算)

所以这个合并的过程类似于并查集,我们只需要维护一个size就可以求出第一问了

对于第二问,我们只需要维护一个最小值和最大值即可(维护最小值是因为有复数)

代码如下

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define debug printf("Now is Line : %d\n",__LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define int long long
#define inf 1234567890000000000
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define _ 300005
int n, m, sa[_], rk[_], tp[_], a[_], he[_], val[_], ans1[_], ans2[_], now, num, b[_];
char c[_];
vector<int> q[_];
struct set {int size, mi, ma, fa;}e[_];
il void Qsort() {
    rep(i, 1, m) a[i] = 0;
    rep(i, 1, n) ++ a[rk[i]];
    rep(i, 1, m) a[i] += a[i - 1];
    drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i];
}
il void get_sort() {
    for(re int w = 1, p = 0; p < n && w <= n; m = p, p = 0, w <<= 1) {
        rep(i, n - w + 1, n) tp[++ p] = i;
        rep(i, 1, n) if(sa[i] > w) tp[++ p] = sa[i] - w;
        Qsort(), swap(tp, rk), rk[sa[1]] = p = 1;
        rep(i, 2, n) rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++ p;
    }
}
il void get_height() {
    int j = 0;
    rep(i, 1, n) {
        if(rk[i] == 1) continue;
        if(j) -- j;
        while(c[i + j] == c[sa[rk[i] - 1] + j]) ++ j;
        he[rk[i]] = j;
    }
}
il int find(int x) {
    while(x != e[x].fa) x = e[x].fa = e[e[x].fa].fa;
    return x;
}
il void merge(int a, int b) {
    int x = find(a), y = find(b);
    now += e[x].size * e[y].size, num = max(num, max(e[x].ma * e[y].ma, e[x].mi * e[y].mi));
    e[y].fa = x, e[x].size += e[y].size, e[x].ma = max(e[x].ma, e[y].ma), e[x].mi = min(e[x].mi, e[y].mi);
}
signed main() {
    n = read(), scanf("%s", c + 1), m = 26, num = -inf;
    rep(i, 1, n) b[i] = read(), rk[i] = c[i] - 'a' + 1, tp[i] = i;
    Qsort(), get_sort(), get_height();
    rep(i, 1, n) e[i].fa = i, e[i].size = 1, e[i].ma = e[i].mi = b[sa[i]], q[he[i]].push_back(i);
    drep(i, 0, n - 1) {
        int pax = q[i].size();
        rep(j, 0, pax - 1) merge(q[i][j], q[i][j] - 1);
        if(now) ans1[i] = now, ans2[i] = num;
    }
    rep(i, 0, n - 1) printf("%lld %lld\n", ans1[i], ans2[i]);
    return 0;
}