传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=3879 题目大意 给定一个字符串 每次询问这个字符串得一些后缀两两之间的 lcp lcp之和 题解 建立反串的SAM得到后缀树 求点间的LCP转化为LCA 每次建立虚树就好了 constmaxn=500005;typedata=recordfa,len,key:longin

Description (我并不想告诉你题目名字是什么鬼) 有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n]. 现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍. Input 第一行两个正整数n,m,分别表示S的长度以