# Nemlit 的博客

By a konjac

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

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

### 第三次转化

#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
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;
}