#x1081. Yet Another LCP Problem

    ID: 6097 远端评测题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-后缀数组倍增Kasai 算法LCP+RMQST 表单调栈贡献法

Yet Another LCP Problem

Yet Another LCP Problem

题面翻译

记lcp(i,j)lcp(i,j)表示i这个后缀和j这个后缀的最长公共前缀长度

给定一个字符串,每次询问的时候给出两个正整数集合A和B,求

∑i∈A,j∈Blcp(i,j)\sum_{i \in A,j \in B}lcp(i,j) 的值

题目描述

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

You are given a string s s of length n n and q q queries. Each query is a pair of integer sets a1,a2,…,ak a_1, a_2, \dots, a_k and b1,b2,…,bl 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 n and q q ( 1≤n,q≤2⋅105 1 \le n, q \le 2 \cdot 10^5 ) — the length of string s s and the number of queries, respectively.

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

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

The second line of each query contains ki k_i integers a1,a2,…aki a_1, a_2, \dots a_{k_i} ( 1≤a1<a2<⋯<aki≤n 1 \le a_1 < a_2 < \dots < a_{k_i} \le n ) — set a a .

The third line of each query contains li l_i integers b1,b2,…bli b_1, b_2, \dots b_{l_i} ( 1≤b1<b2<⋯<bli≤n 1 \le b_1 < b_2 < \dots < b_{l_i} \le n ) — set b 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 q integers — answers for the queries in the same order queries are given in the input.

样例 #1

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

提示

Description of queries:

  1. In the first query s[1…7]=abacaba s[1 \dots 7] = \text{abacaba} and s[2…7]=bacaba 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…7]=abacaba s[1 \dots 7] = \text{abacaba} , s[2…7]=bacaba s[2 \dots 7] = \text{bacaba} , s[3…7]=acaba s[3 \dots 7] = \text{acaba} and s[7…7]=a 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…7]=abacaba 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…7]=abacaba s[1 \dots 7] = \text{abacaba} and s[5…7]=aba 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$ .