2555: SubString
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 3253 Solved: 975
[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 = 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
Source
显然我们要求当前子串子树的后缀结束结点个数。
要在线实现，用lct维护sam
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define maxn 1200000
using namespace std;
int mask;
char st[];
string chars;
void gets(int mask) {
scanf("%s",st);
chars=st;
for(int j=;j<chars.length();j++) {
mask=(mask*+j)%chars.length();
char t=chars[j];
chars[j]=chars[mask];
chars[mask]=t;
}
}
struct data {
int last,cnt;
int son[maxn][],link[maxn],step[maxn];
data() {last=cnt=;}
struct lct {
int fa[maxn],s[maxn][],v[maxn],tag[maxn];
bool isroot(int x) {return s[fa[x]][]!=x&&s[fa[x]][]!=x;}
void add(int x,int y){if(x) v[x]+=y,tag[x]+=y;}
void pushdown(int x) {
if(tag[x]) {
add(s[x][],tag[x]);add(s[x][],tag[x]);
tag[x]=;
}
}
void push(int x) {
if(!isroot(x)) push(fa[x]);
pushdown(x);
}
void rorate(int x) {
int y=fa[x],z=fa[y];
bool l=(s[y][]==x),r=l^;
if(!isroot(y)) s[z][s[z][]==y]=x;
fa[x]=z;fa[y]=x;s[y][l]=s[x][r];
fa[s[x][r]]=y;s[x][r]=y;
}
void splay(int x) {
push(x);
while(!isroot(x)) {
int y=fa[x],z=fa[y];
if(!isroot(y)) {
if(s[y][]==x^s[z][]==y) rorate(x);
else rorate(y);
}
rorate(x);
}
}
void access(int x) {for(int t=;x;t=x,x=fa[x]) {splay(x);s[x][]=t;}}
void link(int x,int y) {fa[x]=y;access(y);splay(y);add(y,v[x]);}
void cut(int x) {access(x);splay(x);add(s[x][],-v[x]);s[x][]=fa[s[x][]]=;}
}t;
void extend(int c) {
int p=last,np=last=++cnt;step[np]=step[p]+;t.v[np]=;
while(p&&!son[p][c]) son[p][c]=np,p=link[p];
if(!p) link[np]=,t.link(np,);
else {
int q=son[p][c];
if(step[q]==step[p]+) link[np]=q,t.link(np,q);
else {
int nq=++cnt;
memcpy(son[nq],son[q],sizeof(son[q]));
link[nq]=link[q];t.link(nq,link[q]);
link[q]=link[np]=nq;
t.cut(q);t.link(np,nq);t.link(q,nq);
step[nq]=step[p]+;
while(son[p][c]==q&&p) son[p][c]=nq,p=link[p];
}
}
}
void add() {
gets(mask);
int l=chars.length();
for(int i=;i<l;i++) extend(chars[i]-'A');
}
int query() {
gets(mask);
int p=,l=chars.length();
for(int i=;i<l;i++) {
p=son[p][chars[i]-'A'];if(!p) return ;
}
t.splay(p);
return t.v[p];
}
}sam;
int main() {
int Q;scanf("%d",&Q);
scanf("%s",st+);
int len=strlen(st+);
for(int i=;i<=len;i++) sam.extend(st[i]-'A');
while(Q--) {
char s[];
scanf("%s",s);
if(s[]=='A') sam.add();
else {
int ans=sam.query();
printf("%d\n",ans);
mask^=ans;
}
}
}