夏晓光(loveJY)的博客

退役前WC复习QAQ

在天羽斩斩的字符串一文中有这个题的部分题解....

做法就是利用线段树合并维护出所有点的信息,然后对于一些节点出现次数大于k的贡献答案

这个贡献答案的方式可以很大胆,就是枚举所有存在的节点然后贡献上去就好

因为我们根据SAM上根号科技,所有串一起从正确的广义SAM向上跳的复杂度总和是$O(n\sqrt n)$

又因为我们本质上相当于一个节点被他的所有包含他的串都访问了一遍,就对应了子树构成的线段树上存在的叶子节点

又显然的是,线段树其他节点和叶子数量级一样,所以我们复杂度还是$O(n\sqrt n)$

空间瓶颈在于线段树合并,完全可以再用一次根号科技代替...

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 7;
const int MAXT = 4e6 + 7;
int root[MAXN];
ll ans[MAXN];
int n, k, ml, cnt;

namespace seg {//线段树
#define mid ((l+r)>>1)
	int ls[MAXT], rs[MAXT], T;
	int sum[MAXT];//存在性
	int sum2[MAXT];//出现性
	inline void add(int &k, int l, int r, int P) {//单点加
		if(!k)k = ++T;
		if(l == r) {
			sum[k] = 1;//!!
			sum2[k]++;//这数组开小了
			return;
		}
		if(P <= mid)add(ls[k], l, mid, P);
		else add(rs[k], mid + 1, r, P);
		sum[k] = sum[ls[k]] + sum[rs[k]];
		sum2[k] = sum2[ls[k]] + sum2[rs[k]];
	}
	inline int merge(int x, int y, int l, int r) {
		if(!x || !y)return (x | y);
		int k = ++T;
		if(l == r) {//只代表一个串
			sum[k] = sum[x] | sum[y];
			sum2[k] = sum2[x] + sum2[y];
			return k;
		}
		ls[k] = merge(ls[x], ls[y], l, mid);
		rs[k] = merge(rs[x], rs[y], mid + 1, r);
		sum[k] = sum[ls[k]] + sum[rs[k]];//这样还是保险点...
		sum2[k] = sum2[ls[k]] + sum2[rs[k]];
		return k;
	}
	inline void dfs(int k, int l, int r, int V) {
		if(!k)return;
		cnt++;
		if(l == r) {
			ans[l] += 1ll * V * sum2[k]; //这个串对应的子树中出现了多少次
			return;
		}
		dfs(ls[k], l, mid, V);
		dfs(rs[k], mid + 1, r, V);
	}
}

int ch[MAXN][26], fa[MAXN], len[MAXN], lst, T;
inline void ins(int c, int x) {//插入第x的字符串
	int p = lst;
	int q, nq;
	if(ch[p][c]) {
		q = ch[p][c];
		if(len[q] == len[p] + 1) {
			lst = q;
			seg::add(root[q], 1, n, x);
			return;
		}
		nq = ++T;
		len[nq] = len[p] + 1;
		memcpy(ch[nq], ch[q], sizeof(ch[q]));
		fa[nq] = fa[q];
		fa[q] = nq;
		lst = nq;
		for(; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
		seg::add(root[nq], 1, n, x);
		return;
	}
	int np = lst = ++T;
	len[np] = len[p] + 1;
	for(; !ch[p][c] && p; p = fa[p])ch[p][c] = np;
	seg::add(root[np], 1, n, x);
	if(!p)fa[np] = 1;
	else {
		q = ch[p][c];
		if(len[q] == len[p] + 1) {
			fa[np] = q;
			return ;
		}
		nq = ++T;
		len[nq] = len[p] + 1;
		memcpy(ch[nq], ch[q], sizeof(ch[q]));
		fa[nq] = fa[q];
		fa[np] = fa[q] = nq;
		for(; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
	}
}

string s[MAXN];
int a[MAXN], c[MAXN];

inline void solve1() {
	for(int i = 1; i <= T; ++i)c[len[i]]++;
	for(int i = 1; i <= ml; ++i)c[i] += c[i - 1];
	for(int i = 1; i <= T; ++i) {
		a[c[len[i]]--] = i;
	}
	for(int i = T; i ; --i) {
		int u = a[i];
		if(seg::sum[root[u]] >= k)
			seg::dfs(root[u], 1, n, len[u] - len[fa[u]]); //贡献这里面所有的串
		root[fa[u]] = seg::merge(root[fa[u]], root[u], 1, n);//不会新建立很多节点吧???
	}
	return ;
}

int main() {
	scanf("%d%d", &n, &k);
	lst = T = 1;
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
		lst = 1;
		for(int j = 0; j < (int)s[i].size(); ++j) {
			ins(s[i][j] - 'a', i);
		}
		ml = max(ml, (int)s[i].size());
	}
	solve1();
	for(int i = 1; i <= n; ++i)printf("%lld ", ans[i]);
	return 0;
}

写的时候小心线段树合并叶子节点信息的处理啊!!