P16315 [ICPC 2023 Jinan R] Basic Substring Structure

After finishing the paper *Faster Algorithms for Internal Dictionary Queries*, Xiaoqingyu and Qiyi Hadron decided to create the following problem. Let $\text{lcp}(s, t)$ denote the longest common prefix of strings $s = s_1 s_2 \dots s_n$ and $t = t_1 t_2 \dots t_m$, i.e., the largest integer $k$ such that $0 \le k \le \min(n, m)$ and $s_1 s_2 \dots s_k$ equals $t_1 t_2 \dots t_k$. Xiaoqingyu gives you a non-empty string $s = s_1 s_2 \dots s_n$. Define $f(s) = \sum\limits_{i=1}^{n} \text{lcp}(s, \text{suf}(s, i))$, where $\text{suf}(s, i)$ denotes the suffix of $s$ starting from $s_i$ (i.e., $\text{suf}(s, i) = s_i s_{i+1} \dots s_n$). Note that in this problem, the alphabet contains $n$ letters, not just $26$. For each $i = 1, 2, \cdots, n$, you need to answer the following query: if you must change $s_i$ to another different character $c$ ($c \ne s_i$), choose the best character $c$ and compute the maximum value of $f(s^{(i)})$, where $s^{(i)} = s_1 \dots s_{i-1} c s_{i+1} \dots s_n$.

There are multiple test cases. The first line contains an integer $T$ denoting the number of test cases. For each test case: The first line contains an integer $n$ ($2 \le n \le 2 \times 10^5$), the length of the string. The second line contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le n$), where $s_i$ means the $i$-th character of the string is the $s_i$-th letter in the alphabet. It is guaranteed that the sum of all $n$ over the test cases does not exceed $2 \times 10^5$.

Let $m(i)$ denote the maximum value of $f(s^{(i)})$. To reduce the output size, for each test case output one integer on a single line, which is $\sum\limits_{i=1}^{n} (m(i) \oplus i)$, where $\oplus$ is the bitwise XOR operator.

For the first sample, we first compute $m(1)$. - If we change $s_1$ to $1$, then $f(s^{(1)}) = 4 + 2 + 1 + 0 = 7$. - If we change $s_1$ to $3$ or $4$, then $f(s^{(1)}) = 4 + 0 + 0 + 0 = 4$. Therefore, $m(1) = 7$. Similarly, $m(2) = 6$, $m(3) = 6$, and $m(4) = 4$. So the answer is $(7 \oplus 1) + (6 \oplus 2) + (6 \oplus 3) + (4 \oplus 4) = 15$. Translated by ChatGPT 5