THUWC前集训Day3
T1 Second
后缀的LCP，第一反应就是先建后缀树。
考虑在后缀树上dp。令(f(u))表示(u)的子树的答案（不考虑该子树外的所有后缀和点，并要求子树内所有后缀权值和为1）。
当(u)表示一个后缀，显然(f(u)=0.)否则依次考虑(u)的所有儿子(v). 若只有一个儿子(v,f(u)=f(v)+len(v)-len(u).)
否则，若给(v)的子树分配的权值和为(x),则(f(u)=max((1-x)f(u),x(f(v)+len(v)-len(u)))).显然max中的两个值相等时最优。
复杂度(O(n)),若用sam建有点卡空间，但实现的时候不必真正建出后缀树，依照拓扑序做dp即可。
T2 Third
我的一种奇怪做法，正经一些的是利用矩阵。
先考虑20分的暴力。对于每个询问我们都搞出真正的序列。
令(f(i,c))表示考虑到(i)，结尾字符为(c)的本质不同子序列数量。
原理：原本本质不同的序列的末尾加入该字符后仍本质不同，以及一个仅包含(c)的子序列。
每次询问复杂度(mathcal O(nc).)
考虑本题询问的特性，若将原序列复制一份接在后面，（并将询问离线）就相当于每次询问 (c+A_{pos+1...pos+n}) 的(f(n,d)).
相当于我们要支持，在末尾加一个字符，在开头加一个字符，在开头删除一个字符和询问(f(n,d))。
重定义(f(s,t))为：在当前维护的序列上，以(s)开头，以(t)结尾的本质不同序列数量。
末尾加字符(a_i)：
开头加字符(c)，实际上没必要真的去更新(f),而只需回答(sum_xf(x,d).)
开头删除字符(x=a_{i-n+1})，这个有点毒瘤。考虑逆进行开头加字符的操作（令(g)为删除该字符前的(f)值）：
顺便维护(s_x=sum_{y}f(x,y),t_x=sum_y f(y,x)) 就可以做到移动一格复杂度为(mathcal O(m)),单次询问复杂度(mathcal O(m))
My code