【Ahoi2013】差异

Source and Judge

Ahoi2013
bzoj3238

Record

30min

Analysis

请先思考后再展开

做法一:
sa
求两两lcp之和,则从前往后按排名扫描每个后缀
然后用权值线段树维护【从每个后缀开始到这里的最小值】的和等信息
那么每次就是把比当前hei小的取出来做差,删除掉并等量替换成当前hei
时间nlogn

upd:其实也是可以n的,而且更好些,用的还是你琛爷的套路
从大到小枚举长度,并查集合并的时候把siz乘积累加进答案

做法二:
sam
把串反过来,巧妙的变成【前缀两两的后缀】
这个东西用parent树的性质:两点lca
所以染一下色然后就是求每个节点是多少对染色节点的lca
这个随便统计一下即可
时间为n

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