bzoj 5084 hashit

bzoj 5084 hashit

​​ Description 你有一个字符串S，一开始为空串，要求支持两种操作 在S后面加入字母C 删除S最后一个字母 问每次操作后S有多少个两两不同的连续子串

Input 一行一个字符串Q,表示对S的操作 如果第i个字母是小写字母c,表示第一种加字母c的操作 如果为-表示删除操作，保证所有删除操作前S都非空 |Q|<=10^5

Output 输出|Q|行，第i行表示i个操作之后S内有多少个不同子串

Sample Input aba-caba Sample Output 1 3 5 3 6 9 12 17 HINT

Source By clj

一开始复杂度没想清楚 yy一下开始写 还拿了bzoj rk1

然而discuss里的数据直接让我跑到24s qwq

正解待填坑 蒟蒻我的做法就是暴力回退 发现每回只删除一个 那么只删除一个 在sam上是可以直接暴力 那么删除多个的情况我们一个一个暴力即可

#includeusing namespace std;const int N=1e5+10;char s[N];int ch[N<<1][26],len[N<<1],fa[N<<1],cnt=1,root=1,last=1;int pd[N<<3],top,top1,lst[N<<1],c[N<<1],ans,ed[N<<1];inline void insert1(int x){ ed[cnt+1]=0;int p=last,np=++cnt;len[np]=len[p]+1;c[cnt]=x; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np;pd[++top]=p;lst[++top1]=last; if (!p) fa[np]=root;else{ int q=ch[p][x]; if (len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));ed[cnt]=2; pd[++top]=fa[q];fa[nq]=fa[q];fa[q]=fa[np]=nq;len[nq]=len[p]+1; for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; pd[++top]=p;pd[++top]=q;c[cnt]=x; } }last=np;ans+=len[np]-len[fa[np]];if (ed[cnt]!=2) ed[cnt]=1;}inline void gao(){ if(ed[cnt]==2){ int q=pd[top--],tp1=pd[top--],fq=pd[top--],tp2=pd[top--]; int p=lst[top1--],x=c[cnt];last=p; ans-=len[cnt-1]-len[fa[cnt-1]]; while(p!=tp2) {ch[p][x]=0;p=fa[p];} fa[q]=fq;while(p!=tp1) ch[p][x]=q,p=fa[p]; memset(ch[cnt],0,sizeof(ch[cnt]));--cnt; memset(ch[cnt],0,sizeof(ch[cnt]));--cnt; }else{ int p=lst[top1--],tp=pd[top--],x=c[cnt]; ans-=len[cnt];ans+=len[fa[cnt]];last=p; while(p!=tp) ch[p][x]=0,p=fa[p]; memset(ch[cnt],0,sizeof(ch[cnt]));--cnt; }}int main(){ freopen("bzoj5084.in","r",stdin); //freopen("bzoj5084.out","w",stdout); //double t1=clock(); scanf("%s",s+1); for (int i=1;s[i];++i){ if (s[i]<'a'||s[i]>'z') gao(); else insert1(s[i]-'a'); printf("%d\n",ans); } //double t2=clock(); //printf("%f\n",(t2-t1)/CLOCKS_PER_SEC); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。