1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <iostream>
#include <stack>
#include <cstring>
#include <algorithm>
#define maxn 200010
#define ll long long
#define INF 1000000000
using namespace std;
int n, m;
char s[maxn];
int tax[maxn], tp[maxn], sa[maxn], rk[maxn], M = 255;
void rsort() {
for (int i = 0; i <= M; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) ++tax[rk[i]];
for (int i = 1; i <= M; ++i) tax[i] += tax[i - 1];
for (int i = n; i; --i) sa[tax[rk[tp[i]]]--] = tp[i];
}
int H[maxn];
void init_sa() {
if (n == 1) return sa[1] = rk[1] = 1, void(); int cnt = 1;
for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i; rsort();
for (int k = 1; k < n; k *= 2) {
if (cnt == n) break; M = cnt; cnt = 0;
for (int i = n - k + 1; i <= n; ++i) tp[++cnt] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++cnt] = sa[i] - k;
rsort(); swap(rk, tp); rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; ++i) {
if (tp[sa[i - 1]] != tp[sa[i]] || tp[sa[i - 1] + k] != tp[sa[i] + k]) ++cnt;
rk[sa[i]] = cnt;
}
} int lcp = 0;
for (int i = 1; i <= n; ++i) {
if (lcp) --lcp;
int j = sa[rk[i] - 1];
while (s[j + lcp] == s[i + lcp]) ++lcp;
H[rk[i]] = lcp;
}
}
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
ll v; int k, tag;
} T[maxn * 4];
inline void maintain(int i) {
T[i].v = T[lc].v + T[rc].v;
T[i].k = T[lc].k + T[rc].k;
}
inline void Update(int i) { T[i].v = T[i].k = 0; T[i].tag = 1; }
inline void pushdown(int i) {
int &tag = T[i].tag; if (!tag) return ;
Update(lc); Update(rc);
tag = 0;
}
void update(int i, int l, int r, int k, int v) {
if (l == r) return T[i].v += 1ll * k * v, T[i].k += v, void();
int m = l + r >> 1; pushdown(i);
if (k <= m) update(lc, l, m, k, v);
else update(rc, m + 1, r, k, v);
maintain(i);
}
int query(int i, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (L <= l && r <= R) {
int res = T[i].k;
Update(i); return res;
} int m = l + r >> 1; pushdown(i);
return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
maintain(i);
}
int Log[maxn], st[maxn][21];
void init_st() { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1, st[i][0] = H[i];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int query(int l, int r) {
int k = Log[r - l + 1];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int a[maxn], b[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> s + 1; init_sa(); init_st();
for (int i = 1; i <= m; ++i) {
int p, q; ll ans = 0; cin >> p >> q;
for (int i = 1, x; i <= p; ++i) cin >> x, a[i] = rk[x];
for (int i = 1, x; i <= q; ++i) cin >> x, b[i] = rk[x];
sort(a + 1, a + p + 1); sort(b + 1, b + q + 1); Update(1);
for (int i = 1, j = 1; i <= p; ++i) {
int k = query(1, 0, n, query(a[i - 1] + 1, a[i]), n);
update(1, 0, n, query(a[i - 1] + 1, a[i]), k);
while (j <= q && b[j] < a[i]) update(1, 0, n, query(b[j] + 1, a[i]), 1), ++j;
if (j <= q && b[j] == a[i]) ans += n - sa[a[i]] + 1; ans += T[1].v;
}
for (int i = 1, j = 1; i <= q; ++i) {
int k = query(1, 0, n, query(b[i - 1] + 1, b[i]), n);
update(1, 0, n, query(b[i - 1] + 1, b[i]), k);
while (j <= p && a[j] < b[i]) update(1, 0, n, query(a[j] + 1, b[i]), 1), ++j;
ans += T[1].v;
} cout << ans << "\n";
}
return 0;
}
|