【YBT2023寒假Day14 C】字符串题（SAM）（树链剖分）（线段树）

字符串题

题目链接：YBT2023寒假Day14 C

题目大意

对于一个字符串 S 定义 F(S) 是 fail 树上除了 0 点其它点的深度和。

G(S) 是 S 每个子串 S’ 的 F(S’) 之和。

然后一个空串，每次在后面加一个字符，要你维护这个串的 G 值。

思路

考虑把 G ( S [ 1 , x ] ) G(S[1,x]) G(S[1,x]) 值差分一下，会发现 G ( S [ 1 , i ] ) − G ( S [ 1 , i − 1 ] ) G(S[1,i])-G(S[1,i-1]) G(S[1,i])−G(S[1,i−1]) 的值其实是以 i i i 为结尾的子串的 F F F 值之和。

那从子串变成了一个后缀，看起来就可做很多了，考虑怎么算。

那我们看 fail 树性质，一个字符串 S S S 中 j j j 是 i i i 的祖先当且仅当 S [ 1 , j ] = S [ i − j + 1 , i ] S[1,j]=S[i-j+1,i] S[1,j]=S[i−j+1,i]。

那 F ( S ) F(S) F(S) 就是满足 S [ 1 , j ] = S [ i − j + 1 ] S[1,j]=S[i-j+1] S[1,j]=S[i−j+1] 且 1 ⩽ j < i 1\leqslant j<i 1⩽j<i 的 ( i , j ) (i,j) (i,j) 对数。

那也就是在 S S S 里面选一个前缀，再选一个非前缀，它们相等的方案数。

注意到我们要求的是以 i i i 结尾的 F F F 值之和，那开头就不固定，结尾是固定的。

那 F F F 值是选一个前缀，再一个非前缀，那这个是开头固定，结尾不固定。

那你这个开头固定放在开头不固定里，它不固定了，你这个结尾不固定在结尾固定里面肯定也是不固定。

所以头尾都不固定，只需要两个不是同一个位置的字符串相等即可。

那答案就是所有本质不同的子串的出现次数 x x x 的 ( x 2 ) \binom{x}{2} (2x​) 之和。

那注意到不需要在线，我们可以先建出最后的后缀树。

那我们用一个 d x d_x dx​ 表示每个点 x x x 对于子串的出现次数。

那插入就是把它到祖先路径的 d x d_x dx​ 加一，询问就是所有点的 endpos 大小乘 ( d x 2 ) \binom{d_x}{2} (2dx​​)。

那这个维护这个和不难，我们记录着这个和 s u m sum sum，每次要插入的时候，每个新贡献的值就是它 endpos 集合大小乘上 d x d_x dx​（这个 d x d_x dx​ 还没加 1 1 1），然后你再把 d x d_x dx​ 加一。

那这个是路径加值，路径求和，直接树链剖分线段树维护即可。

复杂度 O ( n log ⁡ 2 n ) O(n\log ^2n) O(nlog2n)

ex：

如果强制在线，我们也可以用 LCT 来维护这棵树，那就也是同样的操作，复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

代码

#include<cstdio>
#include<vector>
#define ll long long
#define mo 1000000007

using namespace std;

const ll N = 4e5 + 100;
ll n, fa[N], sz[N], son[N], dfn[N], top[N], dy[N];
ll lst = 1, tot = 1, pla[N]; 
char s[N];

struct node {
	ll son[26], len, fa;
}d[N];

struct XD_tree {
	ll num[N << 2], f[N << 2], lzy[N << 2];
	
	void up(ll now) {
		num[now] = (num[now << 1] + num[now << 1 | 1]) % mo;
		f[now] = (f[now << 1] + f[now << 1 | 1]) % mo;
	}
	
	void downa(ll now, ll x) {
		(f[now] += x * num[now] % mo) %= mo;
		(lzy[now] += x) %= mo;
	}
	
	void down(ll now) {
		if (lzy[now]) {
			downa(now << 1, lzy[now]); downa(now << 1 | 1, lzy[now]);
			lzy[now] = 0;
		}
	}
	
	void build(ll now, ll l, ll r) {
		if (l == r) {
			num[now] = d[dy[l]].len - d[d[dy[l]].fa].len;
			return ;
		}
		ll mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now);
	}
	
	void update(ll now, ll l, ll r, ll L, ll R, ll x) {
		if (L <= l && r <= R) {
			downa(now, x); return ;
		}
		ll mid = (l + r) >> 1; down(now);
		if (L <= mid) update(now << 1, l, mid, L, R, x);
		if (mid < R) update(now << 1 | 1, mid + 1, r, L, R, x);
		up(now);
	}
	
	ll query(ll now, ll l, ll r, ll L, ll R) {
		if (L <= l && r <= R) return f[now];
		ll mid = (l + r) >> 1; down(now); ll re = 0;
		if (L <= mid) (re += query(now << 1, l, mid, L, R)) %= mo;
		if (mid < R) (re += query(now << 1 | 1, mid + 1, r, L, R)) %= mo;
		return re;
	}
}T;

struct SLPF {
	vector <ll> G[N];
	
	void add(ll x, ll y) {
		G[x].push_back(y);
	}
	
	void dfs0(ll now, ll father) {
		fa[now] = father; sz[now] = 1;
		for (ll i = 0; i < G[now].size(); i++) {
			ll x = G[now][i];
			dfs0(x, now); sz[now] += sz[x];
			if (sz[x] > sz[son[now]]) son[now] = x;
		}
	}
	
	void dfs1(ll now, ll father) {
		dfn[now] = ++dfn[0]; dy[dfn[0]] = now;
		if (son[now]) {
			top[son[now]] = top[now]; dfs1(son[now], now);
		}
		for (ll i = 0; i < G[now].size(); i++) {
			ll x = G[now][i]; if (x == son[now]) continue;
			top[x] = x; dfs1(x, now);
		}
	}
	
	void build() {
		dfs0(1, 0); top[1] = 1; dfs1(1, 0);
		T.build(1, 1, tot);
	}
	
	void update_root(ll now) {
		while (now) {
			T.update(1, 1, tot, dfn[top[now]], dfn[now], 1);
			now = fa[top[now]];
		}
	}
	
	ll query_root(ll now) {
		ll re = 0;
		while (now) {
			(re += T.query(1, 1, tot, dfn[top[now]], dfn[now])) %= mo;
			now = fa[top[now]];
		}
		return re;
	}
}P;

struct SAM {
	ll insert(ll x) {
		ll p = lst, np = ++tot; lst = np;
		d[np].len = d[p].len + 1;
		for (; p && !d[p].son[x]; p = d[p].fa) d[p].son[x] = np;
		if (!p) d[np].fa = 1;
			else {
				ll q = d[p].son[x];
				if (d[q].len == d[p].len + 1) d[np].fa = q;
					else {
						ll nq = ++tot; d[nq] = d[q];
						d[nq].len = d[p].len + 1;
						d[q].fa = d[np].fa = nq;
						for (; p && d[p].son[x] == q; p = d[p].fa) d[p].son[x] = nq;
					}
			}
		return np;
	}
	
	void build() {
		for (ll i = 2; i <= tot; i++) P.add(d[i].fa, i);
	}
}S;

int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	
	scanf("%lld", &n);
	scanf("%s", s + 1);
	for (ll i = 1; i <= n; i++) pla[i] = S.insert(s[i] - 'a');
	S.build(); P.build();
	
	ll sum = 0, ans = 0;
	for (ll i = 1; i <= n; i++) {
		(sum += P.query_root(pla[i])) %= mo;
		P.update_root(pla[i]);
		(ans += sum) %= mo;
		printf("%lld\n", ans);
	}
	
	return 0;
}