Basic Substring Structure
在编写论文 Faster Algorithms for Internal Dictionary Queries 后,小青鱼和奇异强子决定提出这道题。
对于字符串 s=s1s2…sn 和 t=t1t2…tm,令 lcp(s,t) 表示它们最长公共前缀的长度,即满足 0≤k≤min(n,m) 且 s1…sk=t1…tk 的最大整数 k。
小青鱼给你一个非空字符串 s=s1s2…sn。令 suf(s,i)=sisi+1…sn,并定义
$$f(s)=\sum_{i=1}^{n}\operatorname{lcp}\bigl(s,\operatorname{suf}(s,i)\bigr).$$
请注意,本题的字母表包含 n 种字母。
对于每个位置 i=1,2,…,n,分别进行如下询问:你必须把 si 修改为另一个不同的字母 c=si,得到 s(i)=s1…si−1csi+1…sn。请选择最优的 c,求 f(s(i)) 的最大值 m(i)。各位置的询问相互独立,都从原串开始修改。
输入格式
第一行一个整数 T,表示测试数据组数。对每组数据:
第一行一个整数 n(2≤n≤2×105),表示字符串长度。
第二行 n 个整数 s1,…,sn(1≤si≤n),其中 si 表示第 i 个字符是字母表中的第 si 种字母。
保证同一输入文件所有测试数据的 n 之和不超过 2×105。原题未另给 T 的上限;由总限制及 n≥2 可推出 T≤100000。
输出格式
为了减少输出量,对每组数据输出一行一个整数
i=1∑n(m(i)⊕i),
其中 ⊕ 表示按位异或,外层是普通整数求和,不取模,位置从 1 开始。
样例
输入:
2
4
2 1 1 2
12
1 1 4 5 1 4 1 9 1 9 8 10
输出:
15
217
样例说明
第一组数据中,先计算 m(1):
- 把 s1 改成 1,得到 f(s(1))=4+2+1+0=7。
- 把 s1 改成 3 或 4,得到 f(s(1))=4+0+0+0=4。
所以 m(1)=7。类似地,m(2)=6、m(3)=6、m(4)=4,答案为 (7⊕1)+(6⊕2)+(6⊕3)+(4⊕4)=15。