← 返回题目列表

Codeforces · 1073/G

G. 又一个 LCP 问题

中文机器翻译题面 查看原题

令 $$$\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}^{i = k} \sum\limits_{j = 1}^{j = 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}^{i = q}{k_i} \le 2 \cdot 10^5$$$ 和 $$$\sum\limits_{i = 1}^{i = q}{l_i} \le 2 \cdot 10^5$$$。

输出

打印 $$$q$$$ 整数 — 查询的答案与输入中给出的查询顺序相同。

示例

输入 #1

7 4
abacaba
2 2
1 2
1 2
3 1
1 2 3
7
1 7
1
1 2 3 4 5 6 7
2 2
1 5
1 5

输出 #1

13
2
12
16

注意

查询说明:

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$$$。