BZOJ2555 SubString
SubString
Problem 2555. -- SubString2555: SubString
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 5267 Solved: 1574
[ Submit][ Status][ Discuss]
Description
懒得写背景了，给你一个字符串init，要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符串s在当前字符串中出现了几次？(作为连续子串) 你必须在线支持这些操作。Input
第一行一个数Q表示操作个数 第二行一个字符串表示初始字符串init 接下来Q行，每行2个字符串Type,Str Type是ADD的话表示在后面插入字符串。 Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。 为了体现在线操作，你需要维护一个变量mask，初始值为0 读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。 询问的时候，对TrueStr询问后输出一行答案Result 然后mask=maskxorResult 插入的时候，将TrueStr插到当前字符串后面即可。 HINT:ADD和QUERY操作的字符串都需要解压 长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000 新加数据一组--2015.05.20
Output
Sample Input
2A
QUERY B
ADD BBABBBBAAB
Sample Output
0HINT
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。Source
[ Submit][ Status][ Discuss] HOME Back
分析
所谓的出现次数就是这个字符串在SAM上跑完对应的right集合。要支持及时插入，也就是要动态的维护Parent树的形态。
“动态”，“树”，我们很明显本能的会想到动态树。此处动态树肯定是LCT。
回顾Parent tree的性质, 一个父亲节点所表示的所有子串的出现位置相同，并且为其所有子节点的子串的出现位置的集合的并。这个性质就是解决这道题的关键。
所以我们可以用link-cut-tree维护这一棵Parent tree（因为要支持加边，同时必须在线）。在插入一个字符时, 对其所对应的parent tree上到根的路径上的节点全部加1. 查询时直接输出一个点上的值即可。
路径修改，单点查询，LCT的权能。
当然这个LCT不是我们平时见到的那种LCT。原因：
- 这是一棵有向树。换而言之，这题不可能有换根操作。（SAM的Parent树的形态是相对固定的）
- 注意link和cut的时候要消除之前的影响，体现在标记上。
- 查询的时候如果没有转移边(trans)可走，证明这个子串就没有出现过。
查询的时候要把到根路径上的标记清空，这个splay一下就行了。
时间复杂度\(O((Q+n)\log n+L)\)
代码
两天没打代码SAM都生疏了，竟然把后面的边连向了cur……
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0;rg char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') data=-data;
for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
return data;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
int mask;
char s[3000001];
void gets(int mask){ // edit 1: afferent "mask"
scanf("%s",s);int n=strlen(s);
for(int i=0;i<n;++i){
mask=(mask*131+i)%n;
std::swap(s[i],s[mask]);
}
}
co int N=12e5;
// Link Cut Tree
namespace T{
int fa[N],ch[N][2],val[N],tag[N];
#define lc ch[x][0]
#define rc ch[x][1]
void add(int x,int v) {if(x) val[x]+=v,tag[x]+=v;}
void pushdown(int x){
if(tag[x]){
add(lc,tag[x]),add(rc,tag[x]);
tag[x]=0;
}
}
bool nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void rotate(int x){
int y=fa[x],z=fa[y],l=x==ch[y][1],r=l^1;
if(nroot(y)) ch[z][y==ch[z][1]]=x;fa[x]=z;
ch[y][l]=ch[x][r],fa[ch[x][r]]=y;
ch[x][r]=y,fa[y]=x;
}
void splay(int x){
static int st[N];
int y=x,z=0;
st[++z]=y;
while(nroot(y)) st[++z]=y=fa[y];
while(z) pushdown(st[z--]);
for(;nroot(x);rotate(x)){
y=fa[x],z=fa[y];
if(nroot(y)) rotate(y==ch[z][1]^x==ch[y][1]?x:y);
}
}
void access(int x){
for(int y=0;x;x=fa[y=x]) splay(x),rc=y;
}
void link(int x,int y){ // virtual edge
fa[x]=y,access(y),splay(y),add(y,val[x]);
}
void cut(int x){
access(x),splay(x),add(lc,-val[x]);
fa[lc]=0,lc=0;
}
}
// Suffix Automaton
namespace SAM{
int last=1,tot=1;
int ch[N][26],fa[N],len[N];
void extend(int c){
int p=last,cur=last=++tot;
len[cur]=len[p]+1,T::val[cur]=1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;
if(!p) fa[cur]=1,T::link(cur,1);
else{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[cur]=q,T::link(cur,q);
else{
int clone=++tot;
memcpy(ch[clone],ch[q],sizeof ch[q]);
fa[clone]=fa[q],len[clone]=len[p]+1,T::link(clone,fa[q]);
fa[cur]=fa[q]=clone,T::link(cur,clone),T::cut(q),T::link(q,clone);
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone; // edit 2:clone
}
}
}
void build(){
scanf("%s",s);int n=strlen(s);
for(int i=0;i<n;++i) extend(s[i]-'A');
}
void add(){
gets(mask);int n=strlen(s);
for(int i=0;i<n;++i) extend(s[i]-'A');
}
int query(){
gets(mask);int n=strlen(s);
int p=1;
for(int i=0;i<n;++i)if(!(p=ch[p][s[i]-'A'])) return 0;
T::splay(p);
return T::val[p];
}
}
int main(){
int q=read<int>();
SAM::build();
while(q--){
scanf("%s",s);
if(*s=='A') SAM::add();
else{
int ans=SAM::query();
printf("%d\n",ans);
mask^=ans;
}
}
return 0;
}
更多精彩
