[BZOJ4199] [Noi2015]品酒大会

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

传送门

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

题目大意

$给定以i开始的所有子串权值为a_i$
$询问所有子串中lcp(i,j)_{(从i开始和从j开始的子串)}<=1..n-1的对数以及\max\{a_i*a_j\}$

题解

第一问
我们先求 $lcp(i,j)=k$ 的对数
对原串的反串建立SAM得到后缀树，后缀树上点表示，原串的前缀串的逆序， $lca即为lcp$ ，树形DP算下贡献即可
第二问
记录每个节点的子树中的max，min值树形DP一下
注意intmax要设到很大大

uses math;
constmaxn=500005;maxint=4611686018427387904;
typedata=recordfa,len:longint; size,ans1,ans2,maxx,minn:int64;tranc:array[0..26]of longint;end;
varx:array[0..2*maxn]of data;w:array[0..4*maxn,1..2]of longint;y,ans1,ans2:array[0..4*maxn]of int64;i,j,k:longint;n,m,tail,tot,len,a,b,pre,num,tt:longint;sum:int64;st:ansistring;
procedure init(a,b:longint);
begin  w[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 insert(a:longint;b:int64);
var p,np,q,nq:longint;
begininc(tot); np:=tot; p:=tail;x[np].len:=x[p].len+1; x[np].size:=1; x[np].maxx:=b; x[np].minn:=b; x[np].ans2:=-maxint; x[np].ans1:=0;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]:=npelsebegin  q:=x[p].tranc[a];if x[q].len=x[p].len+1then x[np].fa:=qelse   begininc(tot); nq:=tot; x[nq]:=x[q]; x[nq].size:=0; x[nq].maxx:=-maxint; x[nq].minn:=maxint;x[q].fa:=nq; x[np].fa:=nq;x[nq].len:=x[p].len+1;while x[p].tranc[a]=q dobeginx[p].tranc[a]:=nq;p:=x[p].fa;end;end;end;tail:=np;
end;procedure dfs(a:longint);
var tt:longint;
begintt:=w[a,2];while tt<>0 dobegindfs(w[tt,1]);x[a].ans1:=x[a].ans1+x[a].size*x[w[tt,1]].size;x[a].size:=x[a].size+x[w[tt,1]].size;if x[a].maxx<>-maxint then x[a].ans2:=max(x[a].ans2,x[a].maxx*x[w[tt,1]].maxx);if x[a].minn<>maxint then x[a].ans2:=max(x[a].ans2,x[a].minn*x[w[tt,1]].minn);x[a].maxx:=max(x[a].maxx,x[w[tt,1]].maxx);x[a].minn:=min(x[a].minn,x[w[tt,1]].minn);tt:=w[tt,2];end;
end;beginreadln(n);readln(st);for i:=1 to n doread(y[i]);x[0].minn:=maxint; x[0].maxx:=-maxint; x[0].size:=0; x[0].ans2:=-maxint;for i:=n downto 1 doinsert(ord(st[i])-96,y[i]);len:=tot+1;for i:=1 to tot doinit(x[i].fa,i);dfs(0);for i:=0 to n doans2[i]:=-maxint;for i:=0 to tot dobegin ans1[x[i].len]:=ans1[x[i].len]+x[i].ans1; ans2[x[i].len]:=max(ans2[x[i].len],x[i].ans2); end;for i:=n-1 downto 0 dobegin ans1[i]:=ans1[i]+ans1[i+1]; if ans1[i+1]<>0 then ans2[i]:=max(ans2[i],ans2[i+1]); end;for i:=0 to n-1 dobeginif ans2[i]=-maxint then ans2[i]:=0;writeln(ans1[i],' ',ans2[i]);end;
end.