CF1073G Yet Another LCP Problem

设 $ \text{LCP}(s, t) $ 表示字符串 $ s $ 和 $ t $ 的最长公共前缀的长度。记 $ s[x \dots y] $ 表示字符串 $ s $ 从下标 $ x $ 到下标 $ y $（包含两端）的子串。例如，若 $ s = $ "abcde"，则 $ s[1 \dots 3] = $ "abc"，$ s[2 \dots 5] = $ "bcde"。 给定一个长度为 $ n $ 的字符串 $ s $ 和 $ q $ 个询问。每个询问包含两个整数集合 $ a_1, a_2, \dots, a_k $ 和 $ b_1, b_2, \dots, b_l $。对于每个询问，计算 $ \sum\limits_{i = 1}^{k} \sum\limits_{j = 1}^{l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])} $。

第一行包含两个整数 $ n $ 和 $ q $（$ 1 \le n, q \le 2 \cdot 10^5 $），分别表示字符串 $ s $ 的长度和询问的数量。 第二行包含一个仅由小写拉丁字母组成的字符串 $ s $（$ |s| = n $）。 接下来的 $ 3q $ 行描述每个询问，每个询问占三行。每个询问的第一行包含两个整数 $ k_i $ 和 $ l_i $（$ 1 \le k_i, l_i \le n $），分别表示集合 $ a $ 和 $ b $ 的大小。 第二行包含 $ k_i $ 个整数 $ a_1, a_2, \dots, a_{k_i} $（$ 1 \le a_1 < a_2 < \dots < a_{k_i} \le n $），表示集合 $ a $。 第三行包含 $ l_i $ 个整数 $ b_1, b_2, \dots, b_{l_i} $（$ 1 \le b_1 < b_2 < \dots < b_{l_i} \le n $），表示集合 $ b $。 保证 $ \sum\limits_{i = 1}^{q}{k_i} \le 2 \cdot 10^5 $ 且 $ \sum\limits_{i = 1}^{q}{l_i} \le 2 \cdot 10^5 $。

输出 $ q $ 个整数，依次表示每个询问的答案。

关于询问的说明： 1. 在第一个询问中，$ s[1 \dots 7] = \text{abacaba} $ 和 $ s[2 \dots 7] = \text{bacaba} $ 被考虑。该询问的答案为 $ \text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{bacaba}) + \text{LCP}(\text{bacaba}, \text{abacaba}) + \text{LCP}(\text{bacaba}, \text{bacaba}) = 7 + 0 + 0 + 6 = 13 $。 2. 在第二个询问中，$ s[1 \dots 7] = \text{abacaba} $，$ s[2 \dots 7] = \text{bacaba} $，$ s[3 \dots 7] = \text{acaba} $ 和 $ s[7 \dots 7] = \text{a} $ 被考虑。该询问的答案为 $ \text{LCP}(\text{abacaba}, \text{a}) + \text{LCP}(\text{bacaba}, \text{a}) + \text{LCP}(\text{acaba}, \text{a}) = 1 + 0 + 1 = 2 $。 3. 在第三个询问中，$ s[1 \dots 7] = \text{abacaba} $ 与所有后缀进行比较。答案为所有非零值之和：$ \text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{acaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{abacaba}, \text{a}) = 7 + 1 + 3 + 1 = 12 $。 4. 在第四个询问中，$ s[1 \dots 7] = \text{abacaba} $ 和 $ s[5 \dots 7] = \text{aba} $ 被考虑。该询问的答案为 $ \text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{aba}, \text{abacaba}) + \text{LCP}(\text{aba}, \text{aba}) = 7 + 3 + 3 + 3 = 16 $。 由 ChatGPT 4.1 翻译