考虑对反串建 SAM，设 \([i, n]\) 的后缀对应 SAM 的点是 \(a_i\)。
那么 \(\text{lcp}(s[i : n], s[j : n]) = \text{len}(\text{lca}(a_i, a_j))\)。
于是问题变成了，给定一些点，统计两两 \(\text{lca}\) 点权之和。
考虑建虚树，枚举每个点 \(u\) 作为 \(\text{lca}\) 的次数。设当前已经考虑过的儿子的 \(sz\) 之和为 \(s\)，那么 \(v\) 作为子树会有 \(s \times sz_v\) 次数的贡献。再乘上 \(len_u\) 累加进答案即可。
若使用 dfs 序 LCA，时间复杂度 \(O((n + \sum t) \log n)\)。
code
// Problem: P7409 SvT
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7409
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 1000100;
const int logn = 22;
int n, m, lsh[maxn << 1], b[maxn], a[maxn * 3];
char s[maxn];
vector<int> G[maxn], T[maxn];
struct SAM {
int lst, tot, fa[maxn], ch[maxn][26], len[maxn];
inline void init() {
for (int i = 1; i <= tot; ++i) {
fa[i] = len[i] = 0;
mems(ch[i], 0);
}
lst = tot = 1;
}
inline void insert(int c) {
int u = ++tot, p = lst;
len[u] = len[p] + 1;
lst = u;
for (; p && !ch[p][c]; p = fa[p]) {
ch[p][c] = u;
}
if (!p) {
fa[u] = 1;
return;
}
int q = ch[p][c];
if (len[q] == len[p] + 1) {
fa[u] = q;
return;
}
int nq = ++tot;
fa[nq] = fa[q];
len[nq] = len[p] + 1;
memcpy(ch[nq], ch[q], sizeof(ch[nq]));
fa[u] = fa[q] = nq;
for (; p && ch[p][c] == q; p = fa[p]) {
ch[p][c] = nq;
}
}
} sam;
int st[logn][maxn], dfn[maxn], tim;
inline int get(int i, int j) {
return dfn[i] < dfn[j] ? i : j;
}
inline int qlca(int x, int y) {
if (x == y) {
return x;
}
x = dfn[x];
y = dfn[y];
if (x > y) {
swap(x, y);
}
++x;
int k = __lg(y - x + 1);
return get(st[k][x], st[k][y - (1 << k) + 1]);
}
void dfs(int u) {
dfn[u] = ++tim;
for (int v : G[u]) {
dfs(v);
st[0][dfn[v]] = u;
}
}
ll f[maxn], ans;
void dfs2(int u) {
for (int v : T[u]) {
dfs2(v);
ans += f[u] * f[v] * sam.len[u];
f[u] += f[v];
}
}
void solve() {
scanf("%d%d%s", &n, &m, s + 1);
sam.init();
for (int i = n; i; --i) {
sam.insert(s[i] - 'a');
b[i] = sam.lst;
}
for (int i = 2; i <= sam.tot; ++i) {
G[sam.fa[i]].pb(i);
}
dfs(1);
for (int j = 1; (1 << j) <= tim; ++j) {
for (int i = 1; i + (1 << j) - 1 <= tim; ++i) {
st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
while (m--) {
int len, tot = 0;
scanf("%d", &len);
for (int i = 1; i <= len; ++i) {
scanf("%d", &a[i]);
a[i] = b[a[i]];
}
sort(a + 1, a + len + 1);
len = unique(a + 1, a + len + 1) - a - 1;
sort(a + 1, a + len + 1, [&](const int &x, const int &y) {
return dfn[x] < dfn[y];
});
for (int i = 1; i <= len; ++i) {
lsh[++tot] = a[i];
if (i > 1) {
lsh[++tot] = qlca(a[i - 1], a[i]);
}
}
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
sort(lsh + 1, lsh + tot + 1, [&](const int &x, const int &y) {
return dfn[x] < dfn[y];
});
for (int i = 2; i <= tot; ++i) {
T[qlca(lsh[i - 1], lsh[i])].pb(lsh[i]);
}
for (int i = 1; i <= len; ++i) {
f[a[i]] = 1;
}
ans = 0;
dfs2(lsh[1]);
printf("%lld\n", ans % 23333333333333333LL);
for (int i = 1; i <= tot; ++i) {
vector<int>().swap(T[lsh[i]]);
f[lsh[i]] = 0;
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}