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)\)的