P16315 [ICPC 2023 Jinan R] 基本子串结构

在编写完论文《Faster Algorithms for Internal Dictionary Queries》后，小青鱼与奇异强子决定编写如下的题目。 令 $\text{lcp}(s,t)$ 表示字符串 $s = s_1 s_2 \dots s_n$ 与 $t = t_1 t_2 \dots t_m$ 的最长公共前缀，也就是最大的整数 $k$ 满足 $0 \le k \le \min(n,m)$ 且 $s_1 s_2 \dots s_k$ 等于 $t_1 t_2 \dots t_k$。 小青鱼给了您一个非空的字符串 $s=s_1 s_2 \dots s_n$。令 $f(s)=\sum\limits_{i=1}^{n} \text{lcp}(s, \text{suf}(s, i))$，其中 $\text{suf}(s, i)$ 表示 $s$ 从 $s_i$ 开始的后缀（即 $\text{suf}(s, i) = s_i s_{i+1} \dots s_n$）。请注意在本题中，字母表中包含了 $n$ 种字母，而不是仅有 $26$ 种。 对每个 $i = 1, 2, \cdots, n$，您需要回答如下询问：如果您必须将 $s_i$ 修改为另一个不同的字符 $c$（$c \ne s_i$），请选择最优的字符 $c$ 并计算 $f(s^{(i)})$ 的最大值，其中 $s^{(i)}=s_1 \dots s_{i-1} c s_{i+1} \dots s_n$。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入一个整数 $n$（$2 \le n \le 2 \times 10^5$）表示字符串的长度。 第二行输入 $n$ 个整数 $s_1,s_2,\dots,s_n$（$1 \le s_i \le n$），其中 $s_i$ 表示字符串的第 $i$ 个字符是字母表中第 $s_i$ 个字母。 保证所有数据 $n$ 之和不超过 $2 \times 10^5$。

令 $m(i)$ 表示 $f(s^{(i)})$ 的最大值。为了减少输出的大小，对于每组测试数据输出一行一个整数表示 $\sum\limits_{i=1}^{n} (m(i) \oplus i)$，其中 $\oplus$ 是按位异或运算符。

对于第一组样例数据，我们首先计算 $m(1)$ 的值。 - 如果将 $s_1$ 修改为 $1$，那么 $f(s^{(1)}) = 4 + 2 + 1 + 0 = 7$。 - 如果将 $s_1$ 修改为 $3$ 或 $4$，那么 $f(s^{(1)}) = 4 + 0 + 0 + 0 = 4$。 因此 $m(1) = 7$。 类似地，$m(2) = 6$，$m(3) = 6$ 以及 $m(4) = 4$。所以答案为 $(7 \oplus 1) + (6 \oplus 2) + (6 \oplus 3) + (4 \oplus 4) = 15$。