题目分析

问题本质

统计所有「r相似」的酒对（即两个后缀的LCP≥r）的数量和这些酒对美味度乘积的最大值。

关键观察

「r相似」的等价定义

两个位置$i$和$j$是「r相似」的当且仅当它们对应的后缀$suffix(i)$和$suffix(j)$的最长公共前缀（LCP）长度至少为$r$。

问题转化

对于每个$r$，需要计算：

• 方案数：$\sum_{i<j} [LCP(i,j) \geq r]$
• 最大美味度：$\max_{i<j, LCP(i,j) \geq r} a_i \times a_j$

算法框架

解法：后缀数组 + 并查集合并（主流解法）

步骤1：构建后缀数组

• 计算后缀数组$SA$、排名数组$Rank$、高度数组$Height$
• $Height[i] = LCP(SA[i], SA[i-1])$

步骤2：按Height值从大到小处理 关键思想：从大到小枚举$r$，逐步合并相邻后缀

• 初始时每个后缀独立
• 按$Height$值从大到小处理，每次合并$Height[i] = r$对应的两个后缀

步骤3：并查集维护连通块信息 每个连通块维护：

• $size$：块内后缀个数（用于计算方案数）
• $max1, max2$：最大的两个$a$值（用于正数乘积）
• $min1, min2$：最小的两个$a$值（用于负数乘积，因为负负得正）

步骤4：信息合并与统计 合并两个块$A$和$B$时：

• 方案数增加：$size_A \times size_B$
• 最大乘积候选：
  • $max1_A \times max1_B$（正正）
  • $min1_A \times min1_B$（负负）
• 更新答案：$ans\_cnt[r] += size_A \times size_B$
• 更新答案：$ans\_max[r] = \max(ans\_max[r], 候选值)$

步骤5：后缀和优化 由于「r相似」包含「(r+1)相似」，需要从大到小累加：

• $cnt[r] = cnt[r] + cnt[r+1] + \cdots + cnt[n-1]$
• $max\_val[r] = \max(max\_val[r], max\_val[r+1], \cdots, max\_val[n-1])$

算法细节

并查集实现细节

• 路径压缩 + 按秩合并
• 合并时维护块内最大值、次大值、最小值、次小值
• 注意初始化：每个位置单独成块

负数的特殊处理

由于$a_i$可能为负数，最大乘积可能来自：

• 两个最大正数的乘积
• 两个最小负数的乘积（负负得正） 因此需要同时维护最大值和最小值信息。

边界情况处理

• $r=0$时：所有$C_n^2$对都是0相似
• 当没有r相似时输出0
• 初始化$ans\_max$为负无穷

复杂度分析

时间复杂度

• 后缀数组构建：$O(n \log n)$ 或 $O(n)$（DC3或SA-IS）
• 并查集操作：$O(n \alpha(n))$
• 排序Height：$O(n \log n)$
• 总复杂度：$O(n \log n)$

空间复杂度

• 后缀数组相关：$O(n)$
• 并查集及相关数组：$O(n)$
• 总空间：$O(n)$

替代解法

解法2：后缀自动机 + 树形DP

1. 构建后缀自动机，得到parent树
2. 每个节点代表一组endpos等价的子串
3. 在parent树上进行树形DP，自底向上合并信息
4. 每个节点对应一个长度区间$[len[link[v]]+1, len[v]]$
5. 对该区间内的所有$r$更新答案

解法3：分治 + 单调栈

利用后缀数组的Height数组：

• 使用分治处理每个区间，统计跨越中点的配对
• 或使用单调栈技巧计算每个Height的管辖区间

实现考虑

数据结构选择

• 后缀数组：实现相对简单，常数较小
• 后缀自动机：理论优美，但实现复杂
• 并查集：需要维护额外信息（最大值、最小值等）

优化技巧

• 使用基数排序构建后缀数组
• 并查集使用路径压缩和按秩合并
• 预处理最大值、最小值信息
• 使用邻接表存储相同Height值的位置

特殊情况

• 所有$a_i$相等（测试点11-12）：简化了最大值计算
• 不存在「10相似」（测试点9-10）：提前终止

总结

本题的核心在于将字符串相似性问题转化为后缀的LCP问题，通过后缀数组和并查集的巧妙结合，在$O(n \log n)$时间内解决问题。关键难点在于理解Height数组的性质，以及如何高效地合并信息并处理负数情况。这是一个经典的NOI级别字符串问题，需要深入理解后缀数据结构的应用。