【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,i])-G(S[1,i-1])$ 的值其实是以 $i$ 为结尾的子串的 $F$ 值之和。
那从子串变成了一个后缀，看起来就可做很多了，考虑怎么算。

那我们看 fail 树性质，一个字符串 $S$ 中 $j$ 是 $i$ 的祖先当且仅当 $S[1,j]=S[i-j+1,i]$。
那 $F(S)$ 就是满足 $S[1,j]=S[i-j+1]$ 且 $1⩽j<i$ 的 $(i,j)$ 对数。
那也就是在 $S$ 里面选一个前缀，再选一个非前缀，它们相等的方案数。

注意到我们要求的是以 $i$ 结尾的 $F$ 值之和，那开头就不固定，结尾是固定的。
那 $F$ 值是选一个前缀，再一个非前缀，那这个是开头固定，结尾不固定。
那你这个开头固定放在开头不固定里，它不固定了，你这个结尾不固定在结尾固定里面肯定也是不固定。
所以头尾都不固定，只需要两个不是同一个位置的字符串相等即可。
那答案就是所有本质不同的子串的出现次数 $x$ 的 $\left(\genfrac{}{}{0ex}{}{x}{2}\right)$ 之和。

---

那注意到不需要在线，我们可以先建出最后的后缀树。
那我们用一个 $d_x$ 表示每个点 $x$ 对于子串的出现次数。
那插入就是把它到祖先路径的 $d_x$ 加一，询问就是所有点的 endpos 大小乘 $\left(\genfrac{}{}{0ex}{}{d_x}{2}\right)$。
那这个维护这个和不难，我们记录着这个和 $sum$，每次要插入的时候，每个新贡献的值就是它 endpos 集合大小乘上 $d_x$（这个 $d_x$ 还没加 $1$），然后你再把 $d_x$ 加一。
那这个是路径加值，路径求和，直接树链剖分线段树维护即可。
复杂度 $O(n{\log }^{2}n)$

---

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

代码

#include<cstdio>
#include<vector>
#define ll long long
#define mo 1000000007using 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;
}