Yet Another LCP Problem
Contest: Educational Codeforces Round 53 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, string suffix structures

Let $$$\text{LCP}(s, t)$$$ be the length of the longest common prefix of strings $$$s$$$ and $$$t$$$. Also let $$$s[x \dots y]$$$ be the substring of $$$s$$$ from index $$$x$$$ to index $$$y$$$ (inclusive). For example, if $$$s = $$$ "abcde", then $$$s[1 \dots 3] =$$$ "abc", $$$s[2 \dots 5] =$$$ "bcde".

You are given a string $$$s$$$ of length $$$n$$$ and $$$q$$$ queries. Each query is a pair of integer sets $$$a_1, a_2, \dots, a_k$$$ and $$$b_1, b_2, \dots, b_l$$$. Calculate $$$\sum\limits_{i = 1}^{i = k} \sum\limits_{j = 1}^{j = l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])}$$$ for each query.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the length of string $$$s$$$ and the number of queries, respectively.

The second line contains a string $$$s$$$ consisting of lowercase Latin letters ($$$|s| = n$$$).

Next $$$3q$$$ lines contains descriptions of queries — three lines per query. The first line of each query contains two integers $$$k_i$$$ and $$$l_i$$$ ($$$1 \le k_i, l_i \le n$$$) — sizes of sets $$$a$$$ and $$$b$$$ respectively.

The second line of each query contains $$$k_i$$$ integers $$$a_1, a_2, \dots a_{k_i}$$$ ($$$1 \le a_1 < a_2 < \dots < a_{k_i} \le n$$$) — set $$$a$$$.

The third line of each query contains $$$l_i$$$ integers $$$b_1, b_2, \dots b_{l_i}$$$ ($$$1 \le b_1 < b_2 < \dots < b_{l_i} \le n$$$) — set $$$b$$$.

It is guaranteed that $$$\sum\limits_{i = 1}^{i = q}{k_i} \le 2 \cdot 10^5$$$ and $$$\sum\limits_{i = 1}^{i = q}{l_i} \le 2 \cdot 10^5$$$.

Output format:
Print $$$q$$$ integers — answers for the queries in the same order queries are given in the input.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Description of queries:

1. In the first query $$$s[1 \dots 7] = \text{abacaba}$$$ and $$$s[2 \dots 7] = \text{bacaba}$$$ are considered. The answer for the query is $$$\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. In the second query $$$s[1 \dots 7] = \text{abacaba}$$$, $$$s[2 \dots 7] = \text{bacaba}$$$, $$$s[3 \dots 7] = \text{acaba}$$$ and $$$s[7 \dots 7] = \text{a}$$$ are considered. The answer for the query is $$$\text{LCP}(\text{abacaba}, \text{a}) + \text{LCP}(\text{bacaba}, \text{a}) + \text{LCP}(\text{acaba}, \text{a}) = 1 + 0 + 1 = 2$$$.
3. In the third query $$$s[1 \dots 7] = \text{abacaba}$$$ are compared with all suffixes. The answer is the sum of non-zero values: $$$\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. In the fourth query $$$s[1 \dots 7] = \text{abacaba}$$$ and $$$s[5 \dots 7] = \text{aba}$$$ are considered. The answer for the query is $$$\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$$$.

Example input:
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

Example output:
13
2
12
16

Editorial:
At first, implement your favourite string suffix structure for comparing pair of suffixes lexicographically fast enough. For example, it's a Suffix Array + linear LCP + Sparse Table. Now we can compare two suffixes $$$i$$$ and $$$j$$$ by finding $$$l = lcp(i, j)$$$ and comparing $$$s[i + l]$$$ with $$$s[j + l]$$$.
We will process queries online. Let current query be a pair of arrays $$$a$$$ ($$$|a| = k$$$) and $$$b$$$ ($$$|b| = l$$$). We will calculate answer in two parts: $$$$$$\sum\limits_{s[a_i \dots n] < s[b_j \dots n]}{lcp(s[a_i \dots n], s[b_j \dots n])} + \sum\limits_{s[a_i \dots n] \ge s[b_j \dots n]}{lcp(s[a_i \dots n], s[b_j \dots n])}.$$$$$$
To calculate the first sum we can sort all $$$c = a + b$$$ suffixes in lexicographical order and maintain some information for prefixes of $$$c$$$. What information we need to maintain? We need some Data Structure which will hold $$$lcp$$$ of suffixes from $$$a$$$. When we process some $$$c_i = b_j$$$ we need just a total sum of all $$$lcp$$$ in the DS. If $$$c_i = a_j$$$, we should add to the DS length of $$$a_j$$$-th suffix. And when we move from $$$c_i$$$ to $$$c_{i + 1}$$$ we must recalculate some $$$lcp$$$. Since $$$c$$$ is sorted, all we need is to set $$$lcp_k = min(lcp_k, lcp(s[c_i \dots n], s[c_{i + 1} \dots n]))$$$.
In fact, this Data Structure is just a $$$map$$$. In this $$$map$$$ we will hold for each length $$$l$$$ number of suffixes with $$$lcp = l$$$ (we will hold only non-zero values). When we should add some suffix $$$a_j$$$, we manually increase some value by one. Setting $$$min$$$ with $$$v = lcp(s[c_i \dots n], s[c_{i + 1} \dots n])$$$ can be done with decreasing maximum in $$$map$$$ while its more than $$$v$$$. It can be proven, that there will be $$$O(|a| + |b|)$$$ operations with $$$map$$$ for one query. The total sum can be maintained in some global variable, which will be recalculated each time $$$map$$$ changes.
To calculate the second sum we can just reverse $$$c$$$ and run the same algorithm. So total complexity is $$$O(n \log^2{n} + (\sum\limits_{i = 1}^{i = q}{k_i} + \sum\limits_{i = 1}^{i = q}{l_i}) \log{n})$$$.