A12231 | $Yet Another LCP Problem$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

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

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

输入 #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

C++ 编辑器

输入

输出