Time Limit: 30 Sec Memory Limit: 512 MB
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
2
A
QUERY B
ADD BBABBBBAAB
A
QUERY B
ADD BBABBBBAAB
Sample Output
0
HINT
Source
Ctsc模拟赛By 洁妹
Solution
SAM+LCT。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=1200100; int Q; char s[3000100]; struct LinkCutTree { int fa[N],son[N][2],lazy[N],Stack[N],sum[N]; bool isRoot(int x) { return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;} void pushdown(int x) { if (lazy[x]) { if (son[x][0]) lazy[son[x][0]]+=lazy[x],sum[son[x][0]]+=lazy[x]; if (son[x][1]) lazy[son[x][1]]+=lazy[x],sum[son[x][1]]+=lazy[x]; lazy[x]=0; } } void Rotate(int x) { int y=fa[x],z=fa[y],l,r; if (son[y][0]==x) l=0;else l=1; r=l^1; if (!isRoot(y)) { if (son[z][0]==y) son[z][0]=x;else son[z][1]=x; } fa[x]=z;fa[y]=x;fa[son[x][r]]=y; son[y][l]=son[x][r];son[x][r]=y; } void splay(int x) { int top=0;Stack[++top]=x; for (int i=x;!isRoot(i);i=fa[i]) Stack[++top]=fa[i]; for (;top;top--) pushdown(Stack[top]); while (!isRoot(x)) { int y=fa[x],z=fa[y]; if (!isRoot(y)) { if ((son[y][0]==x)^(son[z][0]==y)) Rotate(x); else Rotate(y); } Rotate(x); } } void access(int x) { for (int i=0;x;i=x,x=fa[x]) { splay(x); son[x][1]=i; } } void link(int x,int y) { fa[x]=y; access(y); splay(y); lazy[y]+=sum[x]; sum[y]+=sum[x]; } void cut(int x) { access(x); splay(x); if (son[x][0]) lazy[son[x][0]]-=sum[x],sum[son[x][0]]-=sum[x]; son[x][0]=fa[son[x][0]]=0; } int query(int x) { splay(x); return sum[x]; } }LCT; struct SAM { int last,root,cnt,maxlen[N],val[N],a[N][26],father[N]; SAM() { last=root=++cnt;} void extend(int c) { int p=last,np=last=++cnt; maxlen[np]=maxlen[p]+1; LCT.sum[np]=1; while (!a[p][c]&&p) a[p][c]=np,p=father[p]; if (!p) father[np]=root,LCT.link(np,root); else { int q=a[p][c]; if (maxlen[p]+1==maxlen[q]) father[np]=q,LCT.link(np,q); else { int nq=++cnt; maxlen[nq]=maxlen[p]+1; memcpy(a[nq],a[q],sizeof(a[nq])); father[nq]=father[q]; LCT.link(nq,father[q]); father[np]=father[q]=nq; LCT.cut(q); LCT.link(q,nq); LCT.link(np,nq); while (a[p][c]==q) a[p][c]=nq,p=father[p]; } } } int query() { int len=strlen(s),id=1; for (int i=0;i<len;i++) if (a[id][s[i]-'A']) id=a[id][s[i]-'A']; else return 0; return LCT.query(id); } }sam; void decode(int mask) { int len=strlen(s); for (int i=0;i<len;i++) { mask=(mask*131+i)%len; swap(s[i],s[mask]); } } int main() { scanf("%d",&Q); scanf("%s",s); int len=strlen(s); for (int i=0;i<len;i++) sam.extend(s[i]-'A'); int mask=0; while (Q--) { char S[10]; scanf("%s%s",S,s); decode(mask); if (S[0]=='Q') { int ans=sam.query(); mask^=ans; printf("%d\n",ans); }else { int len=strlen(s); for (int i=0;i<len;i++) sam.extend(s[i]-'A'); } } return 0; } |
orz
Orz