序
真的都忘了吗？
正文
原题传送门
简要题义：给你一个长度嵬 \(n\) 的 字符串，对于其任意两个后缀，求累和其除去公共前缀的长度之和
\[ans \ 即 \sum _{1\le i <j \le n}(i + j) - 2 * \sum_{1\le i <j \le n} LCP(i, j) \\ 即 \sum_i (\frac{3}{2}i(i - 1))- \sum_{1\le i <j \le n} LCP(i, j) \\即 \frac{(n-1)n(n + 1)}{2}-\sum_{1\le i <j \le n} LCP(i, j)
\]
运用 SA 求出 ht 之后利用单调栈计算答案即可，注意区间的开和闭,因为 \(LCP(i, j) = min_{i < k \le j}\{ht[k]\}\) 这是显然的，所以能用单调栈来算。找到第一比他小的，原来算过，只算新的就好。
代码
嵬
没有 遇过 某某
[AHOI2013] 差异
原文：https://www.cnblogs.com/zhltao/p/12903150.html
