bzoj 2555 SubString
内容
Description
懒得写背景了,给你一个字符串init,要求你支持两个操作
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次?(作为连续子串)
你必须在线支持这些操作。
Input
第一行一个数Q表示操作个数
第二行一个字符串表示初始字符串init
接下来Q行,每行2个字符串Type,Str
Type是ADD的话表示在后面插入字符串。
Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
为了体现在线操作,你需要维护一个变量mask,初始值为0
读入串Str之后,使用这个过程将之解码成真正询问的串TrueStr。
询问的时候,对TrueStr询问后输出一行答案Result
然后mask = mask xor Result
插入的时候,将TrueStr插到当前字符串后面即可。
HINT:ADD和QUERY操作的字符串都需要解压
Output
Sample Input
2
A
QUERY B
ADD BBABBBBAAB
Sample Output
0
HINT
40 % 的数据字符串最终长度 <= 20000,询问次数<= 1000,询问总长度<=10000
100 % 的数据字符串最终长度 <= 600000,询问次数<= 10000,询问总长度<=3000000
新加数据一组–2015.05.20
题解
加入新节点后,它的祖先的right集合都要加1
因为加入节点的时候Parent树的形态会改变,那就再套个数据结构。。动态树肯定是LCT比较好。。
但是网上说暴力比LCT快4倍= =
还有就是我调了一下午是因为读入的decode写错了。。。。注意mask用的时候不能直接用,要提出来个值。。
#include <cstdio>
#include <cstring>
#define N 1200010
using namespace std;
struct lcts
{
int f[N],ch[N][2],val[N],add[N];
void add_tag(int x,int v){val[x]+=v,add[x]+=v;}
void pushdown(int x)
{
if (add[x])
{
if (ch[x][0]) add_tag(ch[x][0],add[x]);
if (ch[x][1]) add_tag(ch[x][1],add[x]);
add[x]=0;
}
}
int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}
int get_son(int x){return ch[f[x]][1]==x;}
void rot(int x)
{
int fa=f[x],fafa=f[fa],k=get_son(x);
if (!is_root(fa))
ch[fafa][ch[fafa][1]==fa]=x;
ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa;
ch[x][k^1]=fa,f[fa]=x;
f[x]=fafa;
}
void push(int x)
{
if(!is_root(x)) push(f[x]);
pushdown(x);
}
void splay(int x)
{
push(x);
for (int fa;!is_root(x);rot(x))
if (!is_root(fa=f[x]))
rot(get_son(x)==get_son(fa)?fa:x);
}
void access(int x)
{
for (int y=0;x;y=x,x=f[x])
splay(x),ch[x][1]=y/*,update(x)*/;
}
void link(int x,int y){f[x]=y,access(y),splay(y),add_tag(y,val[x]);}
void cut(int x){access(x),splay(x),add_tag(ch[x][0],-val[x]),ch[x][0]=f[ch[x][0]]=0;}
}T;
char s[N],com[100];
int dis[N],fa[N],ch[N][26],sz=1,root=1,last=root,len;
void link(int x,int y){fa[x]=y,T.link(x,y);}
void insert(int x)
{
int now=++sz,pre=last;last=now;
T.val[now]=1;dis[now]=dis[pre]+1;
for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
if (!pre) link(now,root);
else if (dis[pre]==dis[ch[pre][x]]+1) link(now,ch[pre][x]);
else
{
int q=ch[pre][x],nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[q],sizeof ch[nows]);
link(nows,fa[q]),T.cut(q),link(q,nows),link(now,nows);
for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
}
}
int query(char s[])
{
int le=strlen(s),now=root;
for (int i=0;i<le;i++)
if (!ch[now][s[i]-'A'])
return 0;
else now=ch[now][s[i]-'A'];
T.splay(now);
return T.val[now];
}
main()
{
int T,mask=0,las=0;
scanf("%d",&T);
scanf("%s",s+1);
len=strlen(s+1);
for (int i=1;i<=len;i++)
insert(s[i]-'A');
while(T--)
{
scanf("%s%s",com,s);
len=strlen(s);
int te=mask;
for (int i=0;i<len;i++)
{
te=(te*131+i)%len;
char t=s[i];s[i]=s[te],s[te]=t;
}
if (com[0]=='A')
for (int i=0;i<len;i++)
insert(s[i]-'A');
else
las=query(s),printf("%d\n",las),mask^=las;
// printf("%d\n",mask);
}
}