mxqz SA + 莫队 37 分
查看原帖
mxqz SA + 莫队 37 分
131591
蒟蒻君HJT泽渡透香楼主2022/6/12 11:37

AC 的是前三个点和 hack 测试点,Test 4 - 10 WA,感觉没啥问题,字符串长度也开到了 41054\cdot 10^5 ,应该是足够长的?

#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;
}
2022/6/12 11:37
加载中...