AC 的是前三个点和 hack 测试点,Test 4 - 10 WA,感觉没啥问题,字符串长度也开到了 4⋅105 ,应该是足够长的?
#include <bits/stdc++.h>
int n, m, s[400005], ss = 10001, len = 0;
int id[400005], sa[400005], rk[890005], h[19][400005];
int buc[490005], tp[400005], old[890005];
int lm[100005], qloc[400005], Log[400005], Ans1[400005], Ans2[400005];
void build_suffix_array(){
s[len + 1] = -1;
for(int i = 1; i <= len; ++i){
rk[i] = s[i];
++buc[rk[i]];
}
for(int i = 1; i <= ss; ++i) buc[i] += buc[i - 1];
for(int i = len; i; --i) sa[buc[rk[i]]--] = i;
for(int w = 1, p; ; w <<= 1){
p = 0;
memset(buc, 0, sizeof buc);
for(int j = len - w + 1; j <= len; ++j) tp[++p] = j;
for(int j = 1; j <= len; ++j) if(sa[j] > w) tp[++p] = sa[j] - w;
for(int j = 1; j <= len; ++j) ++buc[rk[tp[j]]];
for(int j = 1; j <= ss; ++j) buc[j] += buc[j - 1];
for(int j = len; j; --j) sa[buc[rk[tp[j]]]--] = tp[j];
p = 0;
memcpy(old, rk, sizeof rk);
rk[sa[1]] = ++p;
for(int j = 2; j <= len; ++j){
if(old[sa[j]] == old[sa[j - 1]] && old[sa[j] + w] == old[sa[j - 1] + w])
rk[sa[j]] = p;
else rk[sa[j]] = ++p;
}
if(p == len) break;
}
for(int i = 1, k = 0; i <= len; ++i){
if(k) --k;
while(s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
h[0][rk[i]] = k;
}
for(int i = 1; i <= 18; ++i)
for(int j = 1; j + (1 << i - 1) <= len; ++j)
h[i][j] = std::min(h[i - 1][j], h[i - 1][j + (1 << i - 1)]);
return ;
}
inline int lcp(int x, int y){
if(x == y) return len - sa[x] + 1;
if(x > y) std::swap(x, y);
++x;
int LL = y - x + 1;
return std::min(h[Log[LL]][x], h[Log[LL]][y - (1 << Log[LL]) + 1]);
}
struct Query{
int l, r, id;
}q[100005];
int Last[100005], cnt[100005], blk[400005], Ans = 0, T;
inline bool cmp(Query u, Query v){
if(blk[u.l] == blk[v.l]){
if(blk[u.l] & 1) return u.r < v.r;
return u.r > v.r;
}
return u.l < v.l;
}
inline void walk(int x, int op){
if(id[sa[x]] <= 0) return ;
if(op == 1){
++cnt[id[sa[x]]];
if(cnt[id[sa[x]]] == 1){
Last[id[sa[x]]] = T;
++Ans;
}
}
else {
--cnt[id[sa[x]]];
assert(cnt[id[sa[x]]] >= 0);
if(cnt[id[sa[x]]] == 0){
Ans2[id[sa[x]]] += T - Last[id[sa[x]]];
Last[id[sa[x]]] = 0;
--Ans;
}
}
return ;
}
int main(){
int x, y, z;
freopen("name5.in", "r", stdin);
scanf("%d%d", &n, &m);
int now = 0;
for(int i = 1; i <= 400000; ++i){
Log[i] = now;
if(i == (1 << now + 1)) ++now;
}
for(int i = 1; i <= n; ++i){
int l1, l2;
scanf("%d", &l1);
for(int j = 1; j <= l1; ++j){
scanf("%d", &x);
++x;
s[++len] = x;
id[len] = i;
}
s[++len] = ++ss;
scanf("%d", &l2);
for(int j = 1; j <= l2; ++j){
scanf("%d", &x);
++x;
s[++len] = x;
id[len] = i;
}
s[++len] = ++ss;
}
for(int i = 1; i <= m; ++i){
int L;
scanf("%d", &lm[i]);
qloc[i] = len + 1;
for(int j = 1; j <= lm[i]; ++j){
scanf("%d", &x);
++x;
s[++len] = x;
id[len] = -i;
}
s[++len] = ++ss;
}
build_suffix_array();
for(int i = 1; i <= m; ++i){
q[i].id = i;
int l, r, mid;
l = 1, r = rk[qloc[i]];
while(l < r){
mid = l + r >> 1;
if(lcp(mid, rk[qloc[i]]) >= lm[i]) r = mid;
else l = mid + 1;
}
q[i].l = l;
l = rk[qloc[i]], r = len;
while(l < r){
mid = l + r + 1 >> 1;
if(lcp(mid, rk[qloc[i]]) >= lm[i]) l = mid;
else r = mid - 1;
}
q[i].r = l;
}
int Blen = (int)(std::ceil(sqrt(1ll * 2 * len * len / (1ll * m))));
for(int i = 1; i <= len; ++i) blk[i] = (i + Blen - 1) / Blen;
std::sort(q + 1, q + m + 1, cmp);
int nowl = 1, nowr = 0;
for(int i = 1; i <= m; ++i){
T = i;
while(nowl > q[i].l) walk(--nowl, 1);
while(nowr < q[i].r) walk(++nowr, 1);
while(nowl < q[i].l) walk(nowl++, -1);
while(nowr > q[i].r) walk(nowr--, -1);
Ans1[q[i].id] = Ans;
}
for(int i = 1; i <= n; ++i) if(Last[i]) Ans2[i] += m + 1 - Last[i];
for(int i = 1; i <= m; ++i) printf("%d\n", Ans1[i]);
for(int i = 1; i <= n; ++i) printf("%d ", Ans2[i]);
printf("\n");
return 0;
}