字符串

字符串只会哈希。

后缀数组 SA

暑假就开始看……直到现在才搞明白。

定义 表示排名为 的后缀的位置， 表示以 开头的后缀的排名。有 。

考虑如何求出 数组。

尝试倍增，对于每个长度为 的子串求出它在长度相等子串中的排名。

对于长度为 的子串直接解决。接下来考虑合并。

假设需要求出长度为 的子串之间的排名。将 为第一关键字， （不存在则视为无穷小）为第二关键字排序，就得到了它们的排名。

如此倍增，直到 。此时 即为所求。

采用基数排序，复杂度 。据说还有高妙的 解法，但没必要。

---

height 数组

接下来定义 表示从 开始的后缀的最长公共前缀。

定义 表示排名为 的后缀与排名 的后缀的最长公共前缀，即 。

引理

可以利用引理暴力求出 。复杂度 。

证明、应用等参考 OI Wiki。

---

[NOI2015] 品酒大会

先不考虑第二问。

根据题意，我们只需要求出 的对数，再做一遍后缀和即可。

注意到

考虑将 从打到小插入。每次操作形如合并两段区间，两段区间内最小值均大于当前插入的值。

因此，设左右两段大小分别为 ，则这个点的贡献即为 。

至于第二问，维护每段的最大值与最小值即可。