[UOJ#131][BZOJ4199][NOI2015]品酒大会
试题描述
一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。
在大会的晚餐上，调酒师 Rainbow 调制了 n杯鸡尾酒。这 n杯鸡尾酒排成一行，其中第 i杯酒 （1≤i≤n ） 被贴上了一个标签 si ，每个标签都是 26 个小写英文字母之一。设 Str(l,r)表示第 l杯酒到第 r 杯酒的 r−l+1 个标签顺次连接构成的字符串。若 Str(p,po)=Str(q,qo) ，其中 1≤p≤po≤n ，1≤q≤qo≤n ，p≠q ，po−p+1=qo−q+1=r ，则称第 p 杯酒与第 q 杯酒是“r相似” 的。当然两杯“r相似” （r>1）的酒同时也是“1相似”、“2相似”、…… 、“(r−1)相似”的。特别地，对于任意的 1≤p,q≤n ，p≠q ，第 p 杯酒和第 q 杯酒都是“0相似”的。
在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 i 杯酒 （1≤i≤n ） 的美味度为 ai 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 p 杯酒与第 q 杯酒调兑在一起，将得到一杯美味度为 apaq 的酒。现在请各位品酒师分别对于 r=0,1,2,…,n−1 ，统计出有多少种方法可以选出 2 杯“r相似”的酒,并回答选择 2 杯“r相似”的酒调兑可以得到的美味度的最大值。
输入
输入文件的第 1 行包含 1个正整数 n ，表示鸡尾酒的杯数。
第 2 行包含一个长度为 n 的字符串 S ，其中第 i个字符表示第 i 杯酒的标签。
第 3 行包含 n 个整数，相邻整数之间用单个空格隔开，其中第 i个整数表示第 i杯酒的美味度 ai 。
输出
输出文件包括 n行。第 i 行输出 2 个整数，中间用单个空格隔开。第 1个整数表示选出两杯“(i−1) 相似”的酒的方案数，第 2 个整数表示选出两杯“(i−1)相似”的酒调兑可以得到的最大美味度。若不存在两杯“(i−1)相似”的酒，这两个数均为0 。
输入示例1
10 ponoiiipoi 2 1 4 7 4 8 3 6 4 7
输出示例1
45 56 10 56 3 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0
输入示例2
12 abaabaabaaba 1 -2 3 -4 5 -6 7 -8 9 -10 11 -12
输出示例2
66 120 34 120 15 55 12 40 9 27 7 16 5 7 3 -4 2 -4 1 -4 0 0 0 0
输入示例3
传送门（点击下载）
输出示例3
数据规模及约定
n ≤ 300000, |ai| ≤ 1000000000
题解
一看是串匹配的题，先进行后缀排序，计算LCP。
不难发现“r相似”，随着r的减小，方案数和最大美味度一定不降，所以不妨从n-1到0枚举r，再进行累加。
两个后缀“r相似”当且仅当height数组中两个后缀之间最小值大于等于r，考虑使用并查集，将排好序的每个后缀看成一个节点，两个相邻后缀之间的匹配看成一条边，于是当这个匹配值大于等于r时，把这两个相邻的后缀所在的连通块合并成一个。
需要维护连通块的大小(siz)，连通块中的最小美味度(minv)和最大美味度(maxv)。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 300010
#define oo 1ll << 60
#define LL long long
int n, val[maxn];
char S[maxn];
int m, rank[maxn], height[maxn], Ws[maxn], sa[maxn];
bool cmp(int *a, int p1, int p2, int len) { return a[p1] == a[p2] && a[p1+len] == a[p2+len]; }
void ssort() {
int *x = rank, *y = height;
m = 0; for(int i = 1; i <= n; i++) Ws[i] = 0;
for(int i = 1; i <= n; i++) Ws[x[i] = S[i]]++, m = max(m, (int)S[i]);
for(int i = 1; i <= m; i++) Ws[i] += Ws[i-1];
for(int i = n; i; i--) sa[Ws[x[i]]--] = i;
for(int pos = 0, j = 1; pos < n; j <<= 1, m = pos) {
pos = 0;
for(int i = n - j + 1; i <= n; i++) y[++pos] = i;
for(int i = 1; i <= n; i++) if(sa[i] > j) y[++pos] = sa[i] - j;
for(int i = 1; i <= m; i++) Ws[i] = 0;
for(int i = 1; i <= n; i++) Ws[x[y[i]]]++;
for(int i = 1; i <= m; i++) Ws[i] += Ws[i-1];
for(int i = n; i; i--) sa[Ws[x[y[i]]]--] = y[i];
swap(x, y); pos = 1; x[sa[1]] = 1;
for(int i = 2; i <= n; i++) x[sa[i]] = cmp(y, sa[i], sa[i-1], j) ? pos : ++pos;
}
return ;
}
void calch() {
for(int i = 1; i <= n; i++) rank[sa[i]] = i;
for(int i = 1, j, k = 0; i <= n; height[rank[i++]] = k)
for(k ? k-- : 0, j = sa[rank[i]-1]; S[i+k] == S[j+k]; k++) ;
return ;
}
int fa[maxn], siz[maxn], minv[maxn], maxv[maxn];
int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }
int pos[maxn], cntv[maxn];
LL ansc[maxn], ansm[maxn];
LL max(LL a, LL b, LL c, LL x, LL y, LL z) {
return max(max(max(a * b, b * c), a * c), max(max(x * y, y * z), x * z));
}
int main() {
read(); n = 0;
char tc = Getchar();
while(!isalpha(tc)) tc = Getchar();
while(isalpha(tc)) S[++n] = tc, tc = Getchar();
for(int i = 1; i <= n; i++) val[i] = read();
ssort();
calch();
for(int i = 2; i <= n; i++) cntv[height[i]]++, m = max(m, height[i]);
for(int i = m; i >= 0; i--) cntv[i] += cntv[i+1];
for(int i = n; i > 1; i--) pos[cntv[height[i]]--] = i;
for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1, minv[i] = maxv[i] = val[sa[i]];
for(int i = 0; i <= n; i++) ansm[i] = -oo;
// for(int i = 1; i <= n; i++) printf("%d ", height[i]); putchar('
');
for(int i = 1; i <= n; i++) if(pos[i] > 1) {
// printf("%d
", pos[i]);
int u = findset(pos[i]-1), v = findset(pos[i]);
ansc[height[pos[i]]] += (LL)siz[u] * siz[v];
ansm[height[pos[i]]] = max(ansm[height[pos[i]]], max((LL)minv[u] * minv[v], (LL)maxv[u] * maxv[v]));
siz[u] += siz[v];
minv[u] = min(minv[u], minv[v]); maxv[u] = max(maxv[u], maxv[v]);
siz[v] = minv[v] = maxv[v] = 0;
fa[v] = u;
}
for(int i = n - 1; i >= 0; i--) ansc[i] += ansc[i+1], ansm[i] = max(ansm[i], ansm[i+1]);
for(int i = 0; i < n; i++) {
if(!ansc[i]) ansm[i] = 0;
printf("%lld %lld
", ansc[i], ansm[i]);
}
return 0;
}
哦，原来这题后缀自动机如此简单！
对于第一问求方案数，维护一下 parent 树上每个节点上 right 集合的大小即可；对于第二问求最大值，因为题目要求的是左端的数字，所以把串反过来再维护一下 parent 树上 right 集合中最大、次大、最小、次小值即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 300010
#define maxa 26
#define oo 2147483647
#define ool (1ll << 60)
#define LL long long
char str[maxn];
int n, A[maxn];
LL mxt[maxn], tot[maxn];
struct SAM {
int ToT, rt, lst, fa[maxn<<1], to[maxn<<1][maxa], Max[maxn<<1];
int mx1[maxn<<1], mx2[maxn<<1], mn1[maxn<<1], mn2[maxn<<1], siz[maxn<<1];
int sa[maxn<<1], Ws[maxn];
SAM() { ToT = rt = lst = 1; fa[1] = 0; memset(to[1], 0, sizeof(to[1])); Max[1] = 0; mx1[1] = mx2[1] = -oo; mn1[1] = mn2[1] = oo; }
void getinfo() {
scanf("%s", str); n = strlen(str);
for(int i = 1; i <= n; i++) A[i] = read();
for(int i = 0; i < n; i++) extend(i);
return ;
}
void extend(int pos) {
int x = str[pos] - 'a', p = lst, np = ++ToT; lst = np;
Max[np] = Max[p] + 1; mx1[np] = mn1[np] = A[pos+1]; mx2[np] = -oo; mn2[np] = oo; siz[np] = 1;
while(p && !to[p][x]) to[p][x] = np, p = fa[p];
if(!p){ fa[np] = rt; return ; }
int q = to[p][x];
if(Max[q] == Max[p] + 1){ fa[np] = q; return ; }
int nq = ++ToT; Max[nq] = Max[p] + 1; mx1[nq] = mx2[nq] = -oo; mn1[nq] = mn2[nq] = oo; siz[nq] = 0;
memcpy(to[nq], to[q], sizeof(to[q]));
fa[nq] = fa[q];
fa[q] = fa[np] = nq;
while(p && to[p][x] == q) to[p][x] = nq, p = fa[p];
return ;
}
void build_tot() {
for(int i = 0; i <= n; i++) mxt[i] = -ool;
for(int i = 1; i <= ToT; i++) Ws[Max[i]]++;
for(int i = 1; i <= n; i++) Ws[i] += Ws[i-1];
for(int i = ToT; i; i--) sa[Ws[Max[i]]--] = i;
for(int i = ToT; i; i--) {
int u = sa[i];
if(fa[u]) siz[fa[u]] += siz[u];
tot[Max[u]] += (LL)siz[u] * (siz[u] - 1) >> 1;
if(fa[u]) tot[Max[fa[u]]] -= (LL)siz[u] * (siz[u] - 1) >> 1;
}
return ;
}
void build_mxt() {
for(int i = 0; i <= n; i++) mxt[i] = -ool;
for(int i = 1; i <= ToT; i++) Ws[Max[i]]++;
for(int i = 1; i <= n; i++) Ws[i] += Ws[i-1];
for(int i = ToT; i; i--) sa[Ws[Max[i]]--] = i;
for(int i = ToT; i; i--) {
int u = sa[i];
if(fa[u]) {
if(mx1[fa[u]] < mx1[u]) mx2[fa[u]] = mx1[fa[u]], mx1[fa[u]] = mx1[u];
else if(mx2[fa[u]] < mx1[u]) mx2[fa[u]] = mx1[u];
if(mx1[fa[u]] < mx2[u]) mx2[fa[u]] = mx1[fa[u]], mx1[fa[u]] = mx2[u];
else if(mx2[fa[u]] < mx2[u]) mx2[fa[u]] = mx2[u];
if(mn1[fa[u]] > mn1[u]) mn2[fa[u]] = mn1[fa[u]], mn1[fa[u]] = mn1[u];
else if(mn2[fa[u]] > mn1[u]) mn2[fa[u]] = mn1[u];
if(mn1[fa[u]] > mn2[u]) mn2[fa[u]] = mn1[fa[u]], mn1[fa[u]] = mn2[u];
else if(mn2[fa[u]] > mn2[u]) mn2[fa[u]] = mn2[u];
siz[fa[u]] += siz[u];
}
if(siz[u] > 1) mxt[Max[u]] = max(mxt[Max[u]], max((LL)mx1[u] * mx2[u], (LL)mn1[u] * mn2[u]));
}
return ;
}
} sol1, sol2;
int main() {
int n = read();
sol1.getinfo();
sol1.build_tot();
for(int i = n - 1; i >= 0; i--) sol2.extend(i);
sol2.build_mxt();
for(int i = n - 1; i >= 0; i--) tot[i] += tot[i+1], mxt[i] = max(mxt[i], mxt[i+1]);
for(int i = 0; i < n; i++) printf("%lld %lld
", tot[i], tot[i] ? mxt[i] : 0);
return 0;
}