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
HINT
40 % 的数据字符串最终长度 <= 20000，询问次数<= 1000，询问总长度<= 10000
100 % 的数据字符串最终长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000
新加数据一组--2015.05.20
Source
Ctsc模拟赛By 洁妹
显然我们要求当前子串子树的后缀结束结点个数。
要在线实现，用lct维护sam
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cmath>
6 #include<algorithm>
7 #define maxn 1200000
8 using namespace std;
9 int mask;
10 char st[3000005];
11 string chars;
12 void gets(int mask) {
13 scanf("%s",st);
14 chars=st;
15 for(int j=0;j<chars.length();j++) {
16 mask=(mask*131+j)%chars.length();
17 char t=chars[j];
18 chars[j]=chars[mask];
19 chars[mask]=t;
20 }
21 }
22 struct data {
23 int last,cnt;
24 int son[maxn][26],link[maxn],step[maxn];
25 data() {last=cnt=1;}
26 struct lct {
27 int fa[maxn],s[maxn][2],v[maxn],tag[maxn];
28 bool isroot(int x) {return s[fa[x]][1]!=x&&s[fa[x]][0]!=x;}
29 void add(int x,int y){if(x) v[x]+=y,tag[x]+=y;}
30 void pushdown(int x) {
31 if(tag[x]) {
32 add(s[x][0],tag[x]);add(s[x][1],tag[x]);
33 tag[x]=0;
34 }
35 }
36 void push(int x) {
37 if(!isroot(x)) push(fa[x]);
38 pushdown(x);
39 }
40 void rorate(int x) {
41 int y=fa[x],z=fa[y];
42 bool l=(s[y][1]==x),r=l^1;
43 if(!isroot(y)) s[z][s[z][1]==y]=x;
44 fa[x]=z;fa[y]=x;s[y][l]=s[x][r];
45 fa[s[x][r]]=y;s[x][r]=y;
46 }
47 void splay(int x) {
48 push(x);
49 while(!isroot(x)) {
50 int y=fa[x],z=fa[y];
51 if(!isroot(y)) {
52 if(s[y][0]==x^s[z][0]==y) rorate(x);
53 else rorate(y);
54 }
55 rorate(x);
56 }
57 }
58 void access(int x) {for(int t=0;x;t=x,x=fa[x]) {splay(x);s[x][1]=t;}}
59 void link(int x,int y) {fa[x]=y;access(y);splay(y);add(y,v[x]);}
60 void cut(int x) {access(x);splay(x);add(s[x][0],-v[x]);s[x][0]=fa[s[x][0]]=0;}
61 }t;
62 void extend(int c) {
63 int p=last,np=last=++cnt;step[np]=step[p]+1;t.v[np]=1;
64 while(p&&!son[p][c]) son[p][c]=np,p=link[p];
65 if(!p) link[np]=1,t.link(np,1);
66 else {
67 int q=son[p][c];
68 if(step[q]==step[p]+1) link[np]=q,t.link(np,q);
69 else {
70 int nq=++cnt;
71 memcpy(son[nq],son[q],sizeof(son[q]));
72 link[nq]=link[q];t.link(nq,link[q]);
73 link[q]=link[np]=nq;
74 t.cut(q);t.link(np,nq);t.link(q,nq);
75 step[nq]=step[p]+1;
76 while(son[p][c]==q&&p) son[p][c]=nq,p=link[p];
77 }
78 }
79 }
80 void add() {
81 gets(mask);
82 int l=chars.length();
83 for(int i=0;i<l;i++) extend(chars[i]-'A');
84 }
85 int query() {
86 gets(mask);
87 int p=1,l=chars.length();
88 for(int i=0;i<l;i++) {
89 p=son[p][chars[i]-'A'];if(!p) return 0;
90 }
91 t.splay(p);
92 return t.v[p];
93 }
94 }sam;
95 int main() {
96 int Q;scanf("%d",&Q);
97 scanf("%s",st+1);
98 int len=strlen(st+1);
99 for(int i=1;i<=len;i++) sam.extend(st[i]-'A');
100 while(Q--) {
101 char s[10];
102 scanf("%s",s);
103 if(s[0]=='A') sam.add();
104 else {
105 int ans=sam.query();
106 printf("%d
",ans);
107 mask^=ans;
108 }
109 }
110 } View Code