HNOI2019 JOJO

(此题考查了对KMP的理解以及乱搞能力有理有据的优化)

首先对于可持久化的操作,我们可以将其离线下来并在操作树上dfs。

题意显然可以转化为对一个字符串做KMP,并求$\sum nxt_i$。

现在我们考虑已经有了一些字段,现在要在后面加入一个新的字段,如何计算新字段的贡献。

我们可以从之前的最后一个字符开始跳$nxt$,如果跳到一个位置,它后面正好有一长串长度为$y$的$c$,我们就可以进行匹配。

由于保证了$c$不同于之前的最后一个字符,我们知道如果$nxt$跳到某个字段的中间,那么它是一定没有用的,可以自己yy一下。

所以我们定义$nxt’_i$为从当前的第$i$个字段的最后一个点开始,一直跳KMP的$nxt$所跳到的第一个点所在的字段,满足该点是其所在字段的最后一个字符。

以上算法大概是50分,由于数据过水,实际可以AC。

对于hack数据,我们考虑如何使其复杂度正确。(以下优化借鉴于@142857cs的代码orz)

每次跳$nxt’$时,我们考虑进行一些优化:

如果当前字符串存在周期,我们直接跳到所有周期的第一个。

否则就和原来一样跳$nxt$。

这样显然每次长度至少$/2$,复杂度就不需要均摊了,直接就是$O(nlogn)$

代码:

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

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using std::min;
std::map<std::pair<char,short>,int>ma[100001];
char get(){
char ch=getchar();
while(ch<'a'||ch>'z')ch=getchar();
return ch;
}
int end[100010],pre[100010],cnt,n,length[100010],nxt[100010],ope[100010][2],len,P=998244353,f[100001];
int head[100010],Nxt[200010],b[200010],k,cn;
void push(int s,int t){
Nxt[++k]=head[s];
head[s]=k;
b[k]=t;
}
long long ans[100010],fin[100010],val[100010][3];
inline long long getsum(register long long l,register long long r){
if(l>r)return 0;
return (l+r)*(r-l+1)/2;
}
void dfs(int x,int f){
if(ope[x][0]){
int tem=nxt[len];
++len;
ans[len]=0;
val[len][0]=ope[x][0];
val[len][1]=ope[x][1];
val[len][2]=val[len-1][2]+ope[x][1];
nxt[len]=0;
if(len==1){
ans[len]=getsum(1,val[1][1]-1);
}
else{
int lastgap=len-tem;
while(tem&&(val[tem+1][0]!=ope[x][0]||val[tem+1][1]!=ope[x][1])){
if(tem-nxt[tem]==lastgap)tem=tem%lastgap+lastgap;
lastgap=tem-nxt[tem];
tem=nxt[tem];
}
if(tem||(val[1][0]==ope[x][0]&&val[1][1]<=ope[x][1]))nxt[len]=tem+1;
else nxt[len]=tem;
tem=nxt[len-1];
lastgap=len-1-tem;
long long lastlength=0;
while(lastlength<val[len][1]&&tem){
if(val[tem+1][0]==ope[x][0]&&val[tem+1][1]>lastlength){
ans[len]+=getsum(val[tem][2]+lastlength+1,val[tem][2]+min(val[tem+1][1],val[len][1]));
lastlength=val[tem+1][1];
}
if(tem-nxt[tem]==lastgap)tem=tem%lastgap+lastgap;
lastgap=tem-nxt[tem];
tem=nxt[tem];
}
if(lastlength<val[len][1]&&val[1][0]==val[len][0]){
ans[len]+=getsum(lastlength+1,min(val[len][1],val[1][1]));
lastlength=std::max(lastlength,min(val[len][1],val[1][1]));
ans[len]+=val[1][1]*(val[len][1]-lastlength);
}
ans[len]+=ans[len-1];
}
}
fin[x]=ans[len];
for(int i=head[x];i;i=Nxt[i]){
dfs(b[i],x);
}
if(ope[x][0])--len;
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
void write(long long x){
if(x>9)write(x/10);
putchar((x%10)+'0');
}
signed main(){
scanf("%d",&n);
for(int i=1,opt,x;i<=n;i++){
opt=read(),x=read();
if(opt==1){
ope[i][0]=get();
ope[i][1]=x;
auto y=std::make_pair(ope[i][0],ope[i][1]);
f[i]=ma[f[i-1]][y];
if(!f[i]) ma[f[i-1]][y]=i,push(f[i-1],i),f[i]=i;
}
else{
f[i]=f[x];
}
}
dfs(0,-1);
for(int i=1;i<=n;i++)write(fin[f[i]]%P),putchar('\n');
}
# KMP

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×