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