【题解】[HNOI2019] JOJO

CXY07 · 2021-09-18 16:51:34 · 个人记录

题目链接：[HNOI2019] JOJO

本题解同步发布于 My Blog

题意：

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

在 s 末尾插入连续 x 个字符 c。

将 s 撤回到第 x 次操作之后的状态。

在每次操作后，计算 s 的每一个前缀的最长 \text{border} 的长度和。

计算每一个前缀的最长 \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\sim \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;
}