【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;
}