「NOI2015」品酒大会 - 后缀自动机 | Bill Yang's Blog

「NOI2015」品酒大会 - 后缀自动机

题目大意


题目分析

直接对原串建立后缀自动机。
统计每个结点的$end$-$pos$集合大小,$end$-$pos$集合中最大权,$end$-$pos$集合中最小权(负负得正)。
按照逆拓扑序维护每个结点的答案。
对于新产生的$r$相似的方法数即为:
$cnt[\left|max(now)\right|]+=C_{end\text{-}pos(now)}^2$
对于新产生的答案为:
$ans[\left|max(now)\right|]=\max\lbrace ans[\left|max(now)\right|],end$-$max[now][0]\times end$-$max[now][1],end$-$min[now][0]\times end$-$min[now][1])\rbrace$

但是$r+v(v\ge0)$都可以算作$r$相似。
此时我们对方法数做一个差分,然后对方法数和答案求前缀和即可。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=300005,maxc=26;

int n;
LL cnt[maxn],ans[maxn];

struct SuffixAutomaton {
int size,root,last;
int next[maxn*2],top[maxn*2],Bucket[maxn*2];
LL Max[maxn*2],end_pos[maxn*2],end_max[maxn*2][2],end_min[maxn*2][2];
int child[maxn*2][maxc];
SuffixAutomaton() {
size=0;
root=last=newnode(0);
for(int i=0; i<maxn*2; i++) {
end_max[i][0]=end_max[i][1]=-LLONG_MAX;
end_min[i][0]=end_min[i][1]=LLONG_MAX;
}
}
int newnode(int len) {
size++;
next[size]=0;
Max[size]=len;
memset(child[size],0,sizeof(child[size]));
return size;
}
void insert(int data,LL v) {
int p=last,u=newnode(Max[last]+1);
last=u;
end_pos[u]=1;
end_max[u][0]=end_min[u][0]=v;
for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
if(!p)next[u]=root;
else {
int old=child[p][data];
if(Max[old]==Max[p]+1)next[u]=old;
else {
int New=newnode(Max[p]+1);
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[u]=next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;
}
}
}
void update_max(int index,LL v) {
if(v>end_max[index][0]) {
end_max[index][1]=end_max[index][0];
end_max[index][0]=v;
} else if(v>end_max[index][1])end_max[index][1]=v;
}
void update_min(int index,LL v) {
if(v<end_min[index][0]) {
end_min[index][1]=end_min[index][0];
end_min[index][0]=v;
} else if(v<end_min[index][1])end_min[index][1]=v;
}
void topsort() {
for(int i=1; i<=size; i++)Bucket[Max[i]]++;
for(int i=1; i<=size; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=size; i++)top[Bucket[Max[i]]--]=i;
}
void run() {
topsort();
for(int i=0; i<=n+1; i++)ans[i]=-LLONG_MAX;
for(int i=size; i>=1; i--) {
int now=top[i];
if(end_pos[now]>1) {
cnt[Max[now]]+=(end_pos[now]-1)*end_pos[now]/2; //差分
if(i!=1)cnt[Max[next[now]]]-=(end_pos[now]-1)*end_pos[now]/2;
ans[Max[now]]=max(ans[Max[now]],max(end_max[now][0]*end_max[now][1],end_min[now][0]*end_min[now][1]));
}
if(i!=1) { //维护end-pos
end_pos[next[now]]+=end_pos[now];
update_max(next[now],end_max[now][0]);
update_max(next[now],end_max[now][1]);
update_min(next[now],end_min[now][0]);
update_min(next[now],end_min[now][1]);
}
}
for(int i=n; i>=0; i--)cnt[i]+=cnt[i+1];
for(int i=n; i>=0; i--)ans[i]=max(ans[i],ans[i+1]);
for(int i=0; i<=n; i++)
if(ans[i]==-LLONG_MAX)ans[i]=0;
}
} sam;

char s[maxn];
int a[maxn];

int main() {
n=Get_Int();
scanf("%s",s+1);
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=n; i>=1; i--)sam.insert(s[i]-'a',a[i]);
sam.run();
for(int i=0; i<n; i++)printf("%lld %lld\n",cnt[i],ans[i]);
return 0;
}
姥爷们赏瓶冰阔落吧~
0%