关键词:
2555: SubString
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 1936 Solved: 551
[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
A
QUERY B
ADD BBABBBBAAB
Sample Output
HINT
40 % 的数据字符串最终长度 <= 20000,询问次数<= 1000,询问总长度<= 10000
100 % 的数据字符串最终长度 <= 600000,询问次数<= 10000,询问总长度<= 3000000
新加数据一组--2015.05.20
Source
Solution
论文里最难搞的一道题,谢谢 abclzr队长 的帮助。
一个串在模板串中的出现次数显然就是$|Right(s)|$,然后这个的求法是$Parent$树的子树中的叶子节点个数。
暴力的查询是单次$O(N)$,总体$O(N^{2})$的,所以要利用数据结构LCT维护,实现查询$O(logN)$。
在构建SAM的同时要在LCT上进行相应的Link/Cut操作,在Cut的时候,需要将其贡献减去。
样例有点弱,自己搞了个测试点:
5 ABABA QUERY AB QUERY A ADD BAB QUERY AB QUERY A
2 3 3 4
Code
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define MAXN 1200010 char S[MAXN]; int N,Q,M,ans,Mask; inline void read() { string str=S+1; int mask=Mask; for (int i=0; i<str.length(); i++) { mask=(mask*131+i)%str.length(); swap(str[i],str[mask]); } for (int i=0,tot=0; i<str.length(); i++) S[++tot]=str[i]; } namespace LCT { int fa[MAXN],ch[MAXN][2],val[MAXN],tag[MAXN]; inline bool is_root(int x) {return !fa[x] || ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;} inline void Add(int x,int v) {if (!x) return; val[x]+=v,tag[x]+=v;} inline void Pushdown(int x) {if (tag[x]) Add(ch[x][0],tag[x]),Add(ch[x][1],tag[x]),tag[x]=0;} inline void Rotate(int x) { int y=fa[x],w=ch[y][1]==x,z=fa[y]; ch[y][w]=ch[x][w^1]; if (ch[x][w^1]) fa[ch[x][w^1]]=y; if (ch[z][0]==y) ch[z][0]=x; else if (ch[z][1]==y) ch[z][1]=x; fa[x]=fa[y]; fa[y]=x; ch[x][w^1]=y; } int stack[MAXN]; inline void Splay(int x) { int top=0,t=x,y; stack[++top]=x; while (!is_root(t)) stack[++top]=t=fa[t]; while (top) Pushdown(stack[top--]); while (!is_root(x)) { y=fa[x]; if (!is_root(y)) if ((ch[fa[y]][0]==y)^(ch[y][0]==x)) Rotate(x); else Rotate(y); Rotate(x); } } inline void Access(int x) {for (int y=0; x; y=x,x=fa[x]) Splay(x),ch[x][1]=y;} inline void Link(int x,int y) {fa[x]=y; Access(y); Splay(y); Add(y,val[x]);} inline void Cut(int x) {Access(x); Splay(x); Add(ch[x][0],-val[x]); fa[ch[x][0]]=0,ch[x][0]=0;} }using namespace LCT; namespace SAM { int son[MAXN][27],len[MAXN],par[MAXN]; int root,last,sz; inline void Init() {root=last=sz=1;} inline void Extend(int c) { int cur=++sz,p=last; len[cur]=len[p]+1; LCT::val[cur]=1; while (p && !son[p][c]) son[p][c]=cur,p=par[p]; if (!p) par[cur]=root,LCT::Link(cur,root); else { int q=son[p][c]; if (len[p]+1==len[q]) par[cur]=q,LCT::Link(cur,q); else { int nq=++sz; memcpy(son[nq],son[q],sizeof(son[nq])); len[nq]=len[p]+1,par[nq]=par[q]; LCT::Link(nq,par[nq]); while (p && son[p][c]==q) son[p][c]=nq,p=par[p]; par[cur]=par[q]=nq; LCT::Cut(q); LCT::Link(cur,nq); LCT::Link(q,nq); } } last=cur; } inline void Build() {Init(); for (int i=1; i<=N; i++) Extend(S[i]-'A'+1);} inline void Insert() { read(); M=strlen(S+1); for (int i=1; i<=M; i++) Extend(S[i]-'A'+1); } inline int Query() { read(); M=strlen(S+1); int now=root; for (int i=1; i<=M; i++) if (!son[now][S[i]-'A'+1]) return 0; else now=son[now][S[i]-'A'+1]; LCT::Splay(now); return val[now]; } }using namespace SAM; int main() { scanf("%d",&Q); scanf("%s",S+1); N=strlen(S+1); SAM::Build(); while (Q--) { char opt[10]; scanf("%s%s",opt+1,S+1); switch (opt[1]) { case 'A' : SAM::Insert(); break; case 'Q' : printf("%d\n",ans=SAM::Query()); Mask^=ans; break; } // for (int i=1; i<=sz; i++) printf("%d %d %d %d\n",i,ch[i][0],ch[i][1],val[i]); } return 0; }
太久没看LCT了,出现大片遗忘,背了个模板都能弄错,其实应该先复习一下LCT再写这道题的。
bzoj2555substring后缀自动机+lct
【BZOJ2555】SubStringDescription 懒得写背景了,给你一个字符串init,要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符串s在当前字符串中... 查看详情
bzoj2555substring(后缀自动机,link-cuttree)
【BZOJ2555】SubString(后缀自动机,Link-CutTree)题面BZOJ题解这题看起来不难每次要求的就是(right/endpos)集合的大小所以搞一个(LCT)维护一下(SAM)的(Parent)树就好了但是代码一点都不好写(我还是对着黄学长的调的。。。)于是乎我也... 查看详情
bzoj2555substring——后缀自动机+lct(代码片段)
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2555建立后缀自动机,就可以直接加入新串了;出现次数就是Right集合的大小,需要查询Parent树上的子树和;所以可以用LCT维护Parent树,因为Parent树是有根树所以不需要makeroot;代码中的... 查看详情
●bzoj2555substring
...链:http://www.lydsy.com/JudgeOnline/problem.php?id=2555题解:后缀自动机+LCT 不难发现,对于输入的询问串,在自动机里trans后的到的状态的Right集合的大小就是答案。 那么后缀自动机本身就是支持在线添加的,问题就是如何维护好parent树... 查看详情
bzoj2555substring后缀自动机+lct(代码片段)
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2555 题意概述:给出一个初始字符串,支持两种操作:1、在这个字符串后面接上一个字符串;2、询问一个字符串在当前串中出现的次数。强制在线。 你发现这个东西没有更... 查看详情
bzoj2555substring
...这题我怎么见过……后来想起来是sxysxy说给我的一道后缀自动机+LCT的破题,然后我偏不信这个邪,码了个分块hash试图水过去,然后发现不是TLE就是MLE……没办法,只能乖乖写正解了……加入操作只会在原串末尾加一个字符串,... 查看详情
bzoj2555substring——后缀自动机+lct(代码片段)
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2555要维护right集合的大小。因为fa会变,且fa构成一棵树,所以考虑用LCT来维护……和平常写的LCT不太一样。因为要的值是原树上子树里的值,所以没有makeroot,splay里不维护splay里的子... 查看详情
bzoj2555:substring(代码片段)
显然,在后缀自动机的后缀树上插入一个后缀后,此时表示整串的节点(np)到根的所有节点,其表示的串作为子串的出现次数都要+1;发现需要链修改,动态连边/删边,因此用LCT维护注意:虽然没明确写,但根据讨论区以及做题... 查看详情
bzoj千题计划285:bzoj2555:substring(代码片段)
http://www.lydsy.com/JudgeOnline/problem.php?id=2555 后缀自动机,用LCT维护parent树一个串的出现次数=parent树上其所在状态的子树叶节点|Right|之和若在parent中np的子节点中加一个节点p,设p的|Right|=sum,那么根节点到np的整条链上的所有状... 查看详情
[bzoj2555]substring
考虑在extend($x$)的时候维护SAM中所有串出现的次数,存在每个节点上在$S$的尾部加入一个字符$x$,只有($S$的后缀+$x$)这种串会多出现一次,所以extend完之后把$np$在parent树中的所有祖先答案$+1$在extend的过程中只有常数次切换$par... 查看详情
bzoj2555(后缀自动机+lct)(代码片段)
...)你必须在线支持这些操作。题解做法很自然,建出后缀自动机,维护每个节点的right集合,对于询问直接在sam上跑就好了。然后它是在线的,得用LCT维护。然后细节极多,首先必须维护好树的形态,也就是说不能makeroot,所以我... 查看详情
bzoj2555substring
TimeLimit: 30Sec MemoryLimit: 512MBSubmit: 2430 Solved: 719Description 懒得写背景了,给你一个字符串init,要求你支持两个操作 查看详情
[bzoj2555]substring
bzoj题意给你一个初始模板串,要求资瓷以下两个操作:1、在模板串的末尾接上一个串;2、查询一个串在模板串中出现了多少次。强制在线。sol末尾添加直接\(extend\)。查询一个串的出现次数就是查对应状态的\(right\)集合大小。... 查看详情
bzoj2555substring
Description 懒得写背景了,给你一个字符串init,要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符串s在当前字符串中出现了几次?(作为连续子... 查看详情
bzoj2555substring
算是学会sam了吧……原题: 懒得写背景了,给你一个字符串init,要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符... 查看详情
[bzoj2555]substring(sam+lct)(代码片段)
2555:SubStringTimeLimit:30Sec MemoryLimit:512MBSubmit:4077 Solved:1236[Submit][Status][Discuss]Description懒得写背景了,给你一个字符串init,要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出... 查看详情
bzoj2555substring
蒟蒻有生之年终于切掉了这道题……在陈丽杰的sam课件上就有这道题,但是zcysky太菜一直不敢做。其实现在做一下,发现这个题目并不是太难。所谓的出现次数就是这个字符串在SAM上跑完对应的right集合。要支持及时插入,也就... 查看详情
bzoj2555:substring
Description懒得写背景了,给你一个字符串init,要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次?(作为连续子串)你必须在线支持这些操作。Solution思路比较直观啊首先没有插... 查看详情