[BZOJ3879] SvT

本文主要是介绍[BZOJ3879] SvT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=3879

题目大意

给定一个字符串
每次询问这个字符串得一些后缀两两之间的$lcp$之和

题解

建立反串的SAM得到后缀树
求点间的LCP转化为LCA
每次建立虚树就好了

constmaxn=500005;
typedata=recordfa,len,key:longint;tranc:array[0..26]of longint;end;
varx:array[0..3*maxn]of data;w:array[0..6*maxn,1..2]of longint;fa,t,pos,y,dep,z,clear:array[0..3*maxn]of longint;size:array[0..3*maxn]of longint;st:array[0..3*maxn,0..20]of longint;i,j,k:longint;n,m,tot,tail,len,a,b,top,tt:longint;stt:ansistring;sum:int64;
procedure sort(l,r:longint);
var i,j,a,b:longint;
begini:=l; j:=r; a:=pos[z[(l+r)div 2]];repeatwhile pos[z[i]]<a do inc(i);while a<pos[z[j]] do dec(j);if not (i>j) thenbegin b:=z[i]; z[i]:=z[j]; z[j]:=b; inc(i); dec(j); end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;
procedure sort1(l,r:longint);
var i,j,a,b:longint;
begini:=l; j:=r; a:=pos[clear[(l+r)div 2]];repeatwhile pos[clear[i]]<a do inc(i);while a<pos[clear[j]] do dec(j);if not (i>j) thenbegin b:=clear[i]; clear[i]:=clear[j]; clear[j]:=b; inc(i); dec(j); end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;
procedure insert(a:longint);
var p,np,q,nq:longint;
begininc(tot); np:=tot; p:=tail; x[np].len:=x[p].len+1; x[np].key:=1;while (p<>0)and(x[p].tranc[a]=0) dobeginx[p].tranc[a]:=np;p:=x[p].fa;end;if x[p].tranc[a]=0then x[p].tranc[a]:=npelsebeginq:=x[p].tranc[a];if x[q].len=x[p].len+1then x[np].fa:=qelsebegininc(tot); nq:=tot; x[nq]:=x[q]; x[nq].key:=0;x[nq].len:=x[p].len+1;x[q].fa:=nq; x[np].fa:=nq;while (x[p].tranc[a]=q) dobeginx[p].tranc[a]:=nq;p:=x[p].fa;end;end;end;tail:=np;
end;
procedure init(a,b:longint);
beginw[len,1]:=b;if w[a,2]=0 then w[a,2]:=len else w[w[a,1],2]:=len;w[a,1]:=len; inc(len);
end;
procedure dfs(a:longint);
var tt:longint;
begintt:=w[a,2]; inc(len); pos[a]:=len;if x[a].key=1 then y[n-x[a].len+1]:=a;while tt<>0 dobegindep[w[tt,1]]:=dep[a]+1;dfs(w[tt,1]);tt:=w[tt,2];end;
end;
function lca(a,b:longint):longint;
var i:longint;
beginif dep[a]<dep[b] then begin i:=a; a:=b; b:=i; end;for i:=20 downto 0 doif dep[st[a,i]]>=dep[b]then a:=st[a,i];if a=b then exit(a);for i:=20 downto 0 doif st[a,i]<>st[b,i]then begin a:=st[a,i]; b:=st[b,i]; end;exit(st[a,0]);
end;
procedure solve(a:longint);
var tt:longint;
begintt:=w[a,2];while tt<>0 dobeginsolve(w[tt,1]);         size[a]:=size[a]+size[w[tt,1]];tt:=w[tt,2];end;sum:=sum+(int64(x[a].len-x[x[a].fa].len)*(size[a]-1)*(size[a]))div 2;
end;
begin   readln(n,m);readln(stt); tot:=0; tail:=0;for i:=n downto 1 doinsert(ord(stt[i])-96);len:=tot+1;for i:=1 to tot dobegin init(x[i].fa,i); st[i,0]:=x[i].fa; end;len:=0; dep[0]:=1; dfs(0);for j:=1 to 20 dofor i:=1 to tot dost[i,j]:=st[st[i,j-1],j-1];fillchar(size,sizeof(size),0);for i:=1 to m dobeginread(a); sum:=0; clear[0]:=1; clear[1]:=0;for j:=1 to a dobegin read(z[j]); size[y[z[j]]]:=1; z[j]:=y[z[j]]; end;sort(1,a);top:=1; t[top]:=0;for j:=1 to a dobeginif z[j]=z[j-1] then continue;tt:=lca(z[j],t[top]);while dep[t[top]]>dep[tt] dobeginif dep[t[top-1]]<=dep[tt]thenbeginfa[t[top]]:=tt;size[tt]:=size[tt]+size[t[top]];dec(top);                                   if t[top]<>tt then begin inc(top); t[top]:=tt; inc(clear[0]); clear[clear[0]]:=tt; end;break;end;fa[t[top]]:=t[top-1];size[t[top-1]]:=size[t[top-1]]+size[t[top]];dec(top);end;inc(top); t[top]:=z[j]; inc(clear[0]); clear[clear[0]]:=z[j];end;while top>1 dobeginfa[t[top]]:=t[top-1];size[t[top-1]]:=size[t[top-1]]+size[t[top]];dec(top);end;sum:=0;for j:=1 to clear[0] dosum:=sum+(int64(x[clear[j]].len-x[fa[clear[j]]].len)*(size[clear[j]]-1)*size[clear[j]])div 2;writeln(sum);for j:=1 to clear[0] dobegin size[clear[j]]:=0; fa[clear[j]]:=0; end;end;
end.

这篇关于[BZOJ3879] SvT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---