股市的预测

Source and Judge

bzoj2119

Analysis

请先思考后再展开

先差分一下,就是求形如ABA这样的串,
$|B|=m,lcp(后缀j,后缀i) \geq i-j-M$
如果考虑通常的sa+倒着加入hei,那么就是一个动态开点权值线段树维护次数+启发式合并的事了,复杂度log方

正解:
考虑长度为L的A的贡献,然后每个L分一个段,每个段的第一个是这一段的关键点
考虑到每个长度为L的串只会经过一个关键点,那么对于每个关键点,考虑这上面的串去唯一计数
具体而言,枚举第i个关键点(格子(i-1)L+1)和格子(i-1)L+L+M,考虑分别左边(不包含)和右边(包含)的lcp
那么总共有 $minl+minr-ln+1$
复杂度为调和级数的一个log

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a10e.html
转载请注明出处,谢谢!