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

Nemlit

2019-08-28 12:41:56

Solution

原题意:有多少个串的$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; } ```