题解 P2178 【[NOI2015]品酒大会】
Sai0511
·
·
题解
第600ac，写个题解纪念一下。
设ans1(i)表示选出(i-1)相似酒的方案数，
我们求出$height$数组从大到小排序。
考虑并查集然后一个一个往里面加。
因为我们预先从大到小排序过了所以加的串的前缀一定是最小的，此时根据题意：对于$2$个$r$相似的串，则它们也一定是$0 < r'< r$相似的。
我们同时记录一下并查集每个单元的大小$sz$。
对方案数产生的贡献就是这两个单元的$sz$乘积。（乘法原理。）
对于算$ans2$的贡献，这个就很简单了。
我们维护一下每个并查集单元里的最大值和最小值。
每次更新时就取最大值的乘积和最小值的乘积的较大值。（最小值可能会出现负负得正极大的情况。）
最后再合并统计一下答案即可。
### My code
```cpp
#include <bits/stdc++.h>
using ll = long long;
using std::min;
using std::max;
const int maxn = 3e5 + 10;
const ll inf = 1ll << 62;
int n, m, i, j, k, tot;
char s[maxn];
int v[maxn], fa[maxn], id[maxn];
int cnt[maxn], sa[maxn], sec[maxn], he[maxn], rnk[maxn];
ll mn[maxn], mx[maxn], sz[maxn], ans1[maxn], ans2[maxn];
inline void radix_sort() {
for (int i = 0; i <= m; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) cnt[rnk[sec[i]]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[cnt[rnk[sec[i]]]--] = sec[i];
}
inline void get_sa() {
m = 122, radix_sort();
for (int l = 1, tot; l <= n; m = tot, l <<= 1) {
tot = 0;
for (int i = n - l + 1; i <= n; i++) sec[++tot] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > l) sec[++tot] = sa[i] - l;
radix_sort();
std::swap(rnk, sec), rnk[sa[1]] = tot = 1;
for (int i = 2; i <= n; i++)
rnk[sa[i]] = (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + l] == sec[sa[i - 1] + l]) ? tot : ++tot;
if (tot == n) break;
}
}
inline void get_he() {
for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
for (int i = 1, k = 0; i <= n; i++) {
if (rnk[i] == 1) continue;
if (k) k--;
int j = sa[rnk[i] - 1];
while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
he[rnk[i]] = k;
}
}
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
inline void Union(int u, int v) {
int ru = find(u), rv = find(v);
int x = he[u];
ans1[x] += 1ll * sz[ru] * sz[rv];
ans2[x] = max(ans2[x], max(1ll * mx[ru] * mx[rv], 1ll * mn[ru] * mn[rv]));
mx[ru] = max(mx[ru], mx[rv]), mn[ru] = min(mn[ru], mn[rv]);
fa[rv] = ru, sz[ru] += sz[rv];
}
int main() {
scanf("%d\n%s", &n, s + 1);
for (int i = 1; i <= n; i++)
scanf("%d", v + i);
for (int i = 1; i <= n; i++)
rnk[i] = s[i], sec[i] = i;
get_sa(), get_he();
for (int i = 1; i <= n; i++)
id[i] = fa[i] = i, ans1[i] = 0, ans2[i] = -inf, sz[i] = 1, mx[i] = mn[i] = v[sa[i]];
std::sort(id + 1, id + n + 1, [](int a, int b){return he[a] > he[b];});
for (int i = 1, x, y; i <= n; i++)
if (find(id[i]) != find(id[i] - 1)) Union(id[i], id[i] - 1);
for (int i = n - 2; i >= 0; i--)
ans1[i] += ans1[i + 1], ans2[i] = max(ans2[i], ans2[i + 1]);
for (int i = 0; i < n; i++)
printf("%lld %lld\n", ans1[i], !ans1[i] ? 0 : ans2[i]);
return 0;
}
```