【BZOJ4199】【NOI2015】品酒大会

建出后缀数组,那么枚举相似度,满足条件的一定是连续的若干段。当相似度下降时相当于合并若干相邻的段。

用并查集维护每一段里面的最大最小值和个数。合并时更新答案。

也可以建出后缀树,那么两个后缀的LCP为它们在树上的LCA。

每个点维护子树内后缀个数和最大最小值。从底向上处理,儿子上传信息时在父亲处更新答案。

说点什么

您将是第一位评论人!

提醒
wpDiscuz