C. Prefix of Suffixes
比赛的时候调E,调的心态爆炸,最后一点时间写C,又没冲出来
题目大意
给三个数组\(\{S_n\},\{a_n\},\{b_n\}\),对于每个\(i\)求\(\sum_{j=1}^i\sum_{k=j}^{j+z_j-1}A_kB_j\),其中\(z_i\)表示\(S_{[1,i]}\)和\(S_{[j,i]}\)的最长公共前缀的长度,\(S\)数组强制在线
\[n\le100000 \]题解
设\(f_i\)表示\(i\)的答案
可以把式子转化成\(f_i=f_{i-1}+A_i\sum_{j=1}^iB_j[S_{[j,i]}是S_{[1,i]}的前缀]\)
那么关键就是要求\(\sum_{j=1}^iB_j[S_{[j,i]}是S_{[1,i]}的前缀]\)
相当于要对\(S_{[1,i]}\)的求所有\(border\)的\(B\)之和
设\(g_i=\sum_{j=1}^iB_j[S_{[j,i]}是S_{[1,i]}的前缀]\)
考虑从\(g_{i-1}\)来求\(g_i\),那么要把在\(i-1\)上是\(border\)的,但在\(i\)上不是\(border\)的减去,然后再把\(i\)上长度为\(1\)的\(border\)加上
对于一个\(i\),它的\(border\)集合,就是\(kmp_{i}\)连出来的链,\(i-1\)的\(border\)集合,就是\(kmp_{i-1}\)连出来的链
一个在\(i-1\)的长度为\(l\)的\(border\),在\(i\)中如果还存在,它的长度将变为\(l+1\),也就是\(i\)中的\(border\)集合中应该存在\(l+1\),否则这个\(border\)就是要被删去的\(border\)
这个第一个想法就是用\(bitset\)来实现,但这太暴力了,再考虑其他性质,就是\(i\)的\(border\)集合除去\(1\)后一定是\(i-1\)的集合的子集,于是又有第二个想法,暴力的跳\(kmp\)数组,如果我们的复杂度可以控制在\(O(不同的border)\),那么复杂度就是对的,只有\(kmp_{i}=kmp_{i-1}+1\)的情况会影响复杂度,于是可以预处理一下,让条链的时候,直接跳过\(kmp_{i}=kmp_{i-1}+1\)的情况,这样复杂度就对了,每个\(border\)最多被删一次,所以复杂度是\(O(n)\)的