#P18475. Basic Substring Structure

Basic Substring Structure

Basic Substring Structure

在编写论文 Faster Algorithms for Internal Dictionary Queries 后,小青鱼和奇异强子决定提出这道题。

对于字符串 s=s1s2…sns=s_1s_2\ldots s_n 和 t=t1t2…tmt=t_1t_2\ldots t_m,令 lcp⁡(s,t)\operatorname{lcp}(s,t) 表示它们最长公共前缀的长度,即满足 0≤k≤min⁡(n,m)0\le k\le\min(n,m) 且 s1…sk=t1…tks_1\ldots s_k=t_1\ldots t_k 的最大整数 kk。

小青鱼给你一个非空字符串 s=s1s2…sns=s_1s_2\ldots s_n。令 suf⁡(s,i)=sisi+1…sn\operatorname{suf}(s,i)=s_is_{i+1}\ldots s_n,并定义

$$f(s)=\sum_{i=1}^{n}\operatorname{lcp}\bigl(s,\operatorname{suf}(s,i)\bigr).$$

请注意,本题的字母表包含 nn 种字母。

对于每个位置 i=1,2,…,ni=1,2,\ldots,n,分别进行如下询问:你必须把 sis_i 修改为另一个不同的字母 c≠sic\ne s_i,得到 s(i)=s1…si−1csi+1…sns^{(i)}=s_1\ldots s_{i-1}cs_{i+1}\ldots s_n。请选择最优的 cc,求 f(s(i))f(s^{(i)}) 的最大值 m(i)m(i)。各位置的询问相互独立,都从原串开始修改。

输入格式

第一行一个整数 TT,表示测试数据组数。对每组数据:

第一行一个整数 nn(2≤n≤2×1052\le n\le2\times10^5),表示字符串长度。

第二行 nn 个整数 s1,…,sns_1,\ldots,s_n(1≤si≤n1\le s_i\le n),其中 sis_i 表示第 ii 个字符是字母表中的第 sis_i 种字母。

保证同一输入文件所有测试数据的 nn 之和不超过 2×1052\times10^5。原题未另给 TT 的上限;由总限制及 n≥2n\ge2 可推出 T≤100000T\le100000。

输出格式

为了减少输出量,对每组数据输出一行一个整数

∑i=1n(m(i)⊕i),\sum_{i=1}^{n}\bigl(m(i)\mathbin{\oplus} i\bigr),

其中 ⊕\oplus 表示按位异或,外层是普通整数求和,不取模,位置从 11 开始。

样例

输入:

2
4
2 1 1 2
12
1 1 4 5 1 4 1 9 1 9 8 10

输出:

15
217

样例说明

第一组数据中,先计算 m(1)m(1):

  • 把 s1s_1 改成 11,得到 f(s(1))=4+2+1+0=7f(s^{(1)})=4+2+1+0=7。
  • 把 s1s_1 改成 33 或 44,得到 f(s(1))=4+0+0+0=4f(s^{(1)})=4+0+0+0=4。

所以 m(1)=7m(1)=7。类似地,m(2)=6m(2)=6、m(3)=6m(3)=6、m(4)=4m(4)=4,答案为 (7⊕1)+(6⊕2)+(6⊕3)+(4⊕4)=15(7\oplus1)+(6\oplus2)+(6\oplus3)+(4\oplus4)=15。