【题解】[HNOI2019] JOJO

题目链接：[HNOI2019] JOJO

题意：

维护一个字符串 $s$，支持以下两种操作：

1. 在 $s$ 末尾插入连续 $x$ 个字符 $c$。
2. 将 $s$ 撤回到第 $x$ 次操作之后的状态。

在每次操作后，计算 $s$ 的每一个前缀的最长 $\text{border}$ 的长度和。
$1\le n\le 10^5$。

2019 年 4 月 6 日，HNOI2019 Day 1 赛场上，菜鸡 CXY07 打了这题的 50 分部分分做法，可是下午出成绩的时候发现本题 boom 0。

2019 年 7 月，菜鸡 CXY07 看到了神仙们的题解，但是由于太菜，并没有看懂。

2019 年 10 月，菜鸡 CXY07 深刻研究了 KMP，可是并没有学出什么所以然。

2021 年 9 月 10 日，菜鸡 CXY07 准备回来补坑，结果被此题的可持久化线段树做法劝退。

2021 年 9 月 18 日，菜鸡 CXY07 最终还是学习了此题另一种做法，并且在 1h 切掉此题。

两年前我在 HNOI2019 的赛场上，折戟沉沙。两年后，我从倒下的地方爬起。

我成功了。我不再是以前的那个我了。

以上是整活环节，题解在下面

计算每一个前缀的最长 $\text{border}$ 的长度和，实际上就是 $\sum\limits_{i=1}^n \text{fail}_i$。这让我们想到 $\text{KMP}$。

对于撤回操作，自然可以将操作建成操作树，在上面 $\text{DFS}$ 来计算贡献。

每次，我们将操作树上一个节点的答案分为：该节点父亲的答案 $+$ 当前点的贡献。

当前点的贡献形如加入一段长度为 $x$ 的字符 $c$ 后，这个后缀的最长 $\text{border}$ 和。

如果先不考虑 $\text{KMP}$ 的均摊性质，我们可以把 $(c,x)$ 看作一个新的元素，对这样一个元素的序列进行 $\text{KMP}$。

那么加入一段长度为 $x$ 的字符 $c$ 就相当于在该序列末尾加入一个元素 $(c,x)$，我们希望在计算序列末尾元素的 $\text{fail}$ 的过程中，维护答案的增量。

若在匹配元素 $(c,x)$ 的时候，前缀中匹配到了一个元素 $(c,x')$，那么至少我们可以匹配 $\min(x,x')$ 个字符 $c$ 了，这一部分的贡献便形如一个等差数列求和。

当然，如果在匹配到当前的 $(c,x')$ 之前，有一个更长的前缀，可以匹配 $l$ 个字符 $c$，那么当前的 $(c,x')$ 便只能匹配 $l+1$ ~ $\min(x,x')$ 个 $c$（因为如果 $c$ 的个数 $\le l$，那么就存在一个更长的 $\text{border}$）

还有一种特殊情况，若当前元素 $(c,x)$ 没有办法匹配一个长度 $>0$ 的前缀，但是序列的第一个元素 $(c',x')$ 满足 $c'=c,x'\le x$，则当前元素 $(c,x)$ 也是可以匹配序列的第一个元素的。

这样，我们就在维护二元组序列的同时，维护了答案的增量。

接下来来解决 $\text{KMP}$ 复杂度均摊，导致复杂度无保证的情况。实际上在原数据上，直接均摊也能过

设当前正在考察的，长度为 $p$ 的前缀不是当前序列的 $\text{border}$，对于该前缀的形态进行讨论：

• 若该前缀有一个 $>1$ 的周期，则可以直接跳过所有整周期（因为没必要对一模一样的部分检查多遍）。
• 若该前缀没有 $>1$ 的周期，则直接暴力跳 $\text{fail}$ 指针。

如果有 $>1$ 的周期，直接跳过串长至少减半；如果没有 $>1$ 的周期，说明 $\text{fail}<\dfrac{\text{len}}{2}$，串长仍然减半。

因此，这样处理之后，跳 $\text{fail}$ 的复杂度就不再均摊，而是严格 $\mathcal{O}(\log n)$。

于是我们就把该算法优化到 $\mathcal{O}(n\log n)$，可以通过本题。

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m;
int len[MAXN], fail[MAXN], Ans[MAXN], tot[MAXN];
int fail2[MAXN], ok[MAXN];
bool is1[MAXN];
char _s[10];
pii opt[MAXN], s[MAXN];
vec<pair<int*, int>> stk;
vec<int> G[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

void make(int &x, int y) { stk.pb(mp(&x, x)); x = y; }

void roll(int siz) { 
    while((int)stk.size() > siz) {
        *(stk.back().fst) = stk.back().scd;
        stk.pop_back();
    }
}

int sum(int l, int r) { return ((l + r) * (r - l + 1) >> 1) % mod; }

void modadd(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}

void add(int x, int c, int cnt) {
    int l = ++len[x]; 
    make(s[l].fst, c), make(s[l].scd, cnt);
    make(tot[l], tot[l - 1] + cnt);
    if(l == 1) return modadd(Ans[x], sum(0, cnt - 1)), void();
    int p = fail[l - 1], lim = 1;
    while((~p) && s[p + 1] != s[l]) {
        if(s[p + 1].fst == s[l].fst && s[p + 1].scd >= lim && lim <= cnt) {
            modadd(Ans[x], sum(tot[p] + lim, tot[p] + min(s[p + 1].scd, cnt)));
            lim = min(s[p + 1].scd, cnt) + 1;
        } 
        if(ok[p + 1]) p = fail2[p + 1] - 1;
        else p = fail[p];
    } ++p;
    if(p && ((l - p) << 1) <= l)
        make(ok[l], 1), make(fail2[l], fail[l % (l - p) + (l - p)]);
    if(!p && s[1].fst == c && s[1].scd <= cnt) ++p;
    if(p) {
        if(s[p].scd >= lim && lim <= cnt) {
            modadd(Ans[x], sum(tot[p - 1] + lim, tot[p - 1] + min(s[p].scd, cnt)));
            lim = min(s[p].scd, cnt) + 1;
        } if(p == 1 && lim <= cnt) {
            modadd(Ans[x], tot[p] * (cnt - lim + 1) % mod);
            lim = cnt + 1;
        } return make(fail[l], p), void();
    } else return make(fail[l], p), void();
}

void DFS(int x) {
    int sav = stk.size();
    if(is1[x]) add(x, opt[x].fst, opt[x].scd);
    for(auto to : G[x]) len[to] = len[x], Ans[to] = Ans[x], DFS(to);
    roll(sav);
}

signed main () {
#ifdef FILE
    freopen("jojo.in", "r", stdin);
    freopen("jojo.out", "w", stdout);
#endif
    read(n); fail[0] = -1;
    for(int i = 1, op, x; i <= n; ++i) {
        read(op), read(x);
        if(op == 2) { G[x].pb(i); continue; }
        scanf("%s", _s + 1); opt[i] = mp(_s[1] - 'a' + 1, x), is1[i] = true;
        G[i - 1].pb(i); 
    } DFS(0);
    for(int i = 1; i <= n; ++i) printf("%lld\n", Ans[i]);
    return 0;
}