去年省选的原题, 现在看还是比较容易的。

题目

4516: [Sdoi2016]生成魔咒

Time Limit: \(10\)Sec Memory Limit:\(128\)MB Submit: \(570\) Solved:$ 323$

Description

魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符\(1,2\) 拼凑起来形成一个魔咒串\([1,2]\)。 一个魔咒串\(S\)的非空字串被称为魔咒串\(S\)的生成魔咒。 例如 \(S=[1,2,1]\) 时,它的生成魔咒有 \([1]、[2]、[1,2]、[2,1]、[1,2,1]\) 五种。\(S=[1,1,1]\) 时,它的生成魔咒有 $[1]、[1,1]、[1,1,1] $三种。最初 \(S\) 为空串。共进行 \(n\) 次操作,每次操作是在 \(S\)的结尾加入一个魔咒字符。每次操作后都 需要求出,当前的魔咒串 \(S\) 共有多少种生成魔咒。 ## Input 第一行一个整数 \(n\)。 第二行 \(n\) 个数,第 \(i\) 个数表示第 \(i\) 次操作加入的魔咒字符。 \(1≤n≤100000\)。,用来表示魔咒字符的数字\(x\)满足\(1≤x≤10^9\) ## Output 输出\(n\)行,每行一个数。第\(i\)行的数表示第\(i\)次操作后\(S\)的生成魔咒数量 # 解题报告 学了后缀自动机以后,这个题目就简单许多许多许多了; 在线做,增加一个字符,增加的本质不同子串数量实际上就是\(np\)节点\(max-min+1\); 这在\(SAM\)中就是\(right[np]-right[par[np]]\),因为\(min[x]=max[par[x]]+1\) \(SA\)的做法麻烦一些,可以使用常规的\(splay\)维护,因为只需要找\(sa\)中左右最近的位置,也可以用树状数组/线段树\(splay\)的做法可以看下xym; 三种做法中\(splay\)\(O(nlog^2n)\)的,这个很慢,因为splay是用来搞强制在线的, 这个是伪在线,xym虽然用splay,但只实现了树状数组可以实现的部分功能,拥抱常数; 树状数组那个常数很小,但后缀数组本身常数不小,所以最后跑得也不如后缀自动机快; # 代码 SAM

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<map>
using namespace std;
const int N=100001;
map<int,int> son[N<<1];
int n,val[N<<1],par[N<<1],cnt=1,root=1,last=1;
int np,nq,p,q;
long long ans;
char *cp=(char *) malloc(2000000);
char *os=(char *) malloc(2000000),*ot=os;
inline void in(int &x) {
for (;*cp<'0'||*cp>'9';cp++);
for (x=0;*cp>='0'&&*cp<='9';cp++)
x=x*10+*cp-48;
}
void out(long long x) {
if (x) out(x/10),*ot++=x%10+'0';
}
inline void print(long long &x) {
if (x) out(x); else *ot++='0';
*ot++='\n';
}
inline void insert(int x) {
np=++cnt,p=last; val[np]=val[p]+1;
while (p&&!son[p][x])
son[p][x]=np,p=par[p];
if (!p) par[np]=root;
else {
q=son[p][x];
if (val[p]+1==val[q]) par[np]=q;
else {
nq=++cnt; map<int,int>::iterator i;
for (i=son[q].begin();i!=son[q].end();++i)
son[nq][i->first]=i->second;
val[nq]=val[p]+1,par[nq]=par[q];
par[q]=par[np]=nq;
while (p&&son[p][x]==q) son[p][x]=nq,p=par[p];
}
}
ans+=val[np]-val[par[np]]; print(ans);
last=np;
}
int main() {
// freopen("bzoj4516.in","r",stdin);
// freopen("bzoj4516.out", "w",stdout);
fread(cp,1,2000000,stdin); int i,x;
for (in(n),i=1;i<=n;++i) in(x),insert(x);
fwrite(os,1,ot-os, stdout);
return 0;
}

\(SA+BIT\)

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const int N=100005;
int sa[N],ss[N],wv[N],wa[N],wb[N];
int height[N],f[N][20],rank[N];
int n,a[N],bl[N],br[N],vec[N],tn;
long long ans;
char *cp=(char *)malloc(10000000);
inline bool compare(int *x,int l,int r,int len) {
return x[l]==x[r]&&x[l+len]==x[r+len];
}
void da(int *s,int *sa,int n,int m) {
int i,j,p,*x=wa,*y=wb,*t;
for (i=0;i<m;++i) ss[i]=0;
for (i=0;i<n;++i) ++ss[x[i]=s[i]];
for (i=1;i<m;++i) ss[i]+=ss[i-1];
for (i=n-1;i>=0;--i) sa[--ss[x[i]]]=i;
for (j=1,p=1;j<n&&p<n;m=p,j<<=1) {
for (p=0,i=n-j;i<n;++i) y[p++]=i;
for (i=0;i<n;++i) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<m;++i) ss[i]=0;
for (i=0;i<n;++i) wv[i]=x[y[i]];
for (i=0;i<n;++i) ++ss[wv[i]];
for (i=1;i<m;++i) ss[i]+=ss[i-1];
for (i=n-1;i>=0;--i) sa[--ss[wv[i]]]=y[i];
for (t=x,x=y,y=t,i=1,x[sa[0]]=0,p=1;i<n;++i)
x[sa[i]]=compare(y,sa[i],sa[i-1],j)?p-1:p++;
}
}
inline void in(int &x) {
for (;*cp<'0'||*cp>'9';cp++);
for (x=0;*cp>='0'&&*cp<='9';cp++)
x=x*10+*cp-48;
}
void calheight(int *a, int *sa,int n) {
int i,k,j; height[0]=0;
for (i=1;i<=n;++i) rank[sa[i]]=i;
for (k=0,i=0;i<n;height[rank[i]]=k,++i)
for (k?k--:0,j=sa[rank[i]-1];a[j+k]==a[i+k];++k);
for (i=1;i<=n;++i) f[i][0]=height[i];
for (i=1;i<18;++i)
for (j=1;j<=n;++j) if (j+(1<<i)-1<=n)
f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]);
}
inline int lcp(int l,int r) {
if (l>r) swap(l,r); ++l; int tmp=r-l+1,lg=log2(tmp);
return min(f[l][lg],f[r-(1<<lg)+1][lg]);
}
inline void add_l(int x) {
for (int i=x;i<=n;i+=i&-i) bl[i]=max(bl[i],x);
}
inline void add_r(int x) {
for (int i=x;i;i-=i&-i) br[i]=min(br[i],x);
}
inline int query_l(int x,int tmp=0) {
for (int i=x;i;i-=i&-i) tmp=max(tmp,bl[i]);
return tmp;
}
inline int query_r(int x) {int tmp=n+1;
for (int i=x;i<=n;i+=i&-i) tmp=min(tmp,br[i]);
return tmp;
}
int main() {
// freopen("bzoj4516.in","r",stdin);
// freopen("bzoj4516.out","w",stdout);
fread(cp,1,10000000,stdin); int i,nl,nr;
for (in(n),i=0;i<n;++i) in(a[i]),vec[i]=a[i];
sort(vec,vec+n); tn=unique(vec,vec+n)-vec;
for (i=0;i<n;++i) a[i]=lower_bound(vec,vec+tn,a[i])-vec+1;
for (i=0;i<n/2;++i) swap(a[i],a[n-i-1]);
da(a,sa,n+1,tn+2),calheight(a,sa,n);
memset(bl,0,sizeof(bl)); for(i=1;i<=n;++i) br[i]=n+1;
for (i=n-1;i>=0;--i) {
nl=query_l(rank[i]),nr=query_r(rank[i]);
ans+=n-i,ans+=lcp(nl,nr),ans-=lcp(nl,rank[i])+lcp(rank[i],nr);
printf("%lld\n",ans),add_l(rank[i]),add_r(rank[i]);
}
return 0;
}

UPDATE

之前速度分析都来自理论,后来我生成了极限随机数据进行实测; 只能说完全符合理论分析; splay bit+sa sam 实践是检验真理的唯一标准!

留言