(200)行纯干货的代码，一发(WA)掉真的是让人窒息，幸好最后找到了锅在哪。（差点就要弃掉了(QAQ)）
【调出来的时候真的是要高兴到哭出来了(TwT)】
这个题有很多种写法，但是大多数都是强行水过去的，正解的话应该是(SA)或者(SAM)搞一些数据结构维护。我在这里选择的是线段树维护(RMQ)，第一问就变成了区间颜色个数，第二问把第一问的答案差分对应到每个颜色上。放(SA+)莫队的人好像很少，这里我给一发清新脱俗又臭又长的代码供大家参考。
说句实话，如果我会(SAM)的话绝对不会用这种毒瘤写法。太(TM)难调了。
#include <bits/stdc++.h>
using namespace std;
const int N = 600010;
const int INF = 0x7fffffff;
#define ls (p << 1)
#define rs (p << 1 | 1)
int n, m, l, len, s[N], id[N], height[N];
int sa[N], tp[N], rk[N], _rk[N], bin[N], qry[N], lenq[N];
void base_sort (int n, int m) {
for (int i = 1; i <= m; ++i) bin[i] = 0;
for (int i = 1; i <= n; ++i) bin[rk[tp[i]]]++;
for (int i = 1; i <= m; ++i) bin[i] += bin[i - 1];
for (int i = n; i >= 1; --i) sa[bin[rk[tp[i]]]--] = tp[i];
}
void suffix_sort (int n, int m) {
for (int i = 1; i <= n; ++i) {
rk[i] = s[i], tp[i] = i;
}
base_sort (n, m);
for (int w = 1; w <= n; w <<= 1) {
int cnt = 0;
for (int i = n - w + 1; i <= n; ++i) {
tp[++cnt] = i;
}
for (int i = 1; i <= n; ++i) {
if (sa[i] > w) {
tp[++cnt] = sa[i] - w;
}
}
base_sort (n, m);
memcpy (_rk, rk, sizeof (rk));
rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; ++i) {
rk[sa[i]] = _rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w] ? cnt : ++cnt;
}
if (cnt == n) return;
m = cnt;
}
}
void get_height (int n) {
int k = 0;
for (int i = 1; i <= n; ++i) {
if (k) --k;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k]) ++k;
height[rk[i]] = k;
}
}
struct Segment_Tree {
//维护height数组最小值的线段树
int a[N << 2];
void push_up (int p) {
a[p] = min (a[ls], a[rs]);
}
void build (int l, int r, int p) {
if (l == r) {
a[p] = height[l];
return;
}
int mid = (l + r) >> 1;
build (l, mid, ls);
build (mid + 1, r, rs);
push_up (p);
}
int query (int l, int r, int nl, int nr, int p) {
if (nl <= l && r <= nr) {
return a[p];
}
int mid = (l + r) >> 1, res = INF;
if (nl <= mid) res = min (res, query (l, mid, nl, nr, ls));
if (mid + 1 <= nr) res = min (res, query (mid + 1, r, nl, nr, rs));
return res;
}
}tr;
struct Query {
int l, r, id, blo;
}q[N];
bool cmp (Query lhs, Query rhs) {
return lhs.blo == rhs.blo ? lhs.r < rhs.r : lhs.blo < rhs.blo;
}
bool can_use (int l, int r, int lcp) {
return tr.query (1, len, l, r, 1) >= lcp;
}
int have[N], ans1[N], ans2[N];
int main () {
cin >> n >> m;
int ban = 10001;
s[len = 0] = -1;
for (int i = 1; i <= n; ++i) {
for (int k = 0; k <= 1; ++k) {
cin >> l;
for (int j = 1; j <= l; ++j) {
cin >> s[++len];
id[len] = i;
}
s[++len] = ++ban;
}
}
for (int i = 1; i <= m; ++i) {
cin >> l;
lenq[i] = l;
qry[i] = len + 1;
for (int j = 1; j <= l; ++j) {
cin >> s[++len];
}
s[++len] = ++ban;
}
suffix_sort (len, ban);
get_height (len);
tr.build (1, len, 1);
int maxn = sqrt (len);
for (int i = 1; i <= m; ++i) {
q[i].id = i;
int l = 1, r = rk[qry[i]];
while (l < r) {
int mid = (l + r) >> 1;
if (can_use (mid, r, lenq[i])) {
r = mid;
} else {
l = mid + 1;
}
}
if (height[r] < lenq[i]) r++;
q[i].l = r - 1;
//确认左边界
l = rk[qry[i]], r = len;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (can_use (l, mid, lenq[i])) {
l = mid;
} else {
r = mid - 1;
}
}
if (height[l] < lenq[i]) l--;
q[i].r = l;
//确认右边界
q[i].blo = (q[i].l - 1) / maxn + 1;
//分块
}
sort (q + 1, q + 1 + m, cmp);
int l = 1, r = 0, tot = 0;
for (int i = 1; i <= m; ++i) {
while (l < q[i].l) {
--have[id[sa[l]]];
if (id[sa[l]] != 0 && have[id[sa[l]]] == 0) {
--tot;
ans2[id[sa[l]]] -= (m - i + 1);
}
++l;
}
while (l > q[i].l) {
--l;
if (id[sa[l]] != 0 && have[id[sa[l]]] == 0) {
++tot;
ans2[id[sa[l]]] += (m - i + 1);
}
++have[id[sa[l]]];
}
while (r > q[i].r) {
--have[id[sa[r]]];
if (id[sa[r]] != 0 && have[id[sa[r]]] == 0) {
--tot;
ans2[id[sa[r]]] -= (m - i + 1);
}
--r;
}
while (r < q[i].r) {
++r;
if (id[sa[r]] != 0 && have[id[sa[r]]] == 0) {
++tot;
ans2[id[sa[r]]] += (m - i + 1);
}
++have[id[sa[r]]];
}
ans1[q[i].id] = tot;
}
for (int i = 1; i <= m; ++i) printf ("%d
", ans1[i]);
for (int i = 1; i <= n; ++i) printf ("%d ", ans2[i]);
}