LibreOJ 3055 「HNOI2019」JOJO

首先显然往 KMP 想，但是好像没有限制总长诶那怎么办呢（
考虑把 (x,c) 这个二元组看做一个字符。

求 Fail 的时候除了第一个二元组，别的二元组都要完全匹配。
因为如果仅是 c 相同而 x 不同，下一个字符一定匹配不上，没有什么用。
但是答案是需要这些贡献的。所以一个 Fail 应当造成一个等差数列的贡献。

诶但是有可持久化怎么办呢（
建个操作树递归处理（在线模拟这个也是可以的，只不过要把操作树上的链可持久化下来）。

诶但是 KMP 复杂度不是均摊的吗怎么办呢（
众所周知 AC 自动机暴力跳 Fail 复杂度是错的，所以我们的做法是直接把失配的边连向失配之后该跳到的状态。
KMP 也可以类似这样做，我们就得到了一个叫 KMP 自动机的东西。

然后主席树维护一下边和贡献就可以了（
具体地，注意到对于 i≤x 都有一个 li+i 的形式，其中 li 是 Fail 链上在此处深度最大的贡献。
i 拆出来直接算，li 可以用主席树区间赋值维护。

代码：

#include <cstdio>
#include <cassert>
#include <utility>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int X = 1e4;
const int mod = 998244353;
int n;
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct note
{
    int x,c;
} a[N + 5];
int id[N + 5],ans[N + 5],len[N + 5];
int mx[N + 5][26],rt[N + 5][26];
inline int calc(int n)
{
    return ((long long)n * (n + 1) >> 1) % mod;
}
struct node
{
    int sum,tag;
    int nxt;
    int ls,rs;
} seg[(N << 7) + 5];
int seg_tot;
inline void push(int p,int tl,int tr)
{
    int &tot = seg_tot;
    int mid = tl + tr >> 1;
    if(seg[p].tag)
        seg[++tot] = seg[seg[p].ls],seg[seg[p].ls = tot].sum = (long long)seg[p].tag * (mid - tl + 1) % mod,seg[seg[p].ls].tag = seg[p].tag,
        seg[++tot] = seg[seg[p].rs],seg[seg[p].rs = tot].sum = (long long)seg[p].tag * (tr - mid) % mod,seg[seg[p].rs].tag = seg[p].tag,
        seg[p].tag = 0;
}
void update(int r,int k,int nxt,int &p,int tl,int tr)
{
    int &tot = seg_tot;
    seg[++tot] = seg[p],p = tot;
    if(tr < r)
    {
        seg[p].sum = (long long)k * (tr - tl + 1) % mod,seg[p].tag = k;
        return ;
    }
    if(tl == tr)
    {
        seg[p].sum = (long long)k * (tr - tl + 1) % mod,seg[p].tag = k,seg[p].nxt = nxt;
        return ;
    }
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    update(r,k,nxt,seg[p].ls,tl,mid);
    r > mid && (update(r,k,nxt,seg[p].rs,mid + 1,tr),1);
    seg[p].sum = (seg[seg[p].ls].sum + seg[seg[p].rs].sum) % mod;
}
inline pair<int,int> operator+(const pair<int,int> &a,const pair<int,int> &b)
{
    return make_pair((a.first + b.first) % mod,a.second | b.second);
}
pair<int,int> query(int r,int p,int tl,int tr)
{
    if(tr < r)
        return make_pair(seg[p].sum,0);
    if(tl == tr)
        return make_pair(seg[p].sum,seg[p].nxt);
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    pair<int,int> ret(0,0);
    ret = ret + query(r,seg[p].ls,tl,mid);
    r > mid && (ret = ret + query(r,seg[p].rs,mid + 1,tr),1);
    return ret;
}
int s[N + 5],top;
void dfs(int i)
{
    s[++top] = i;
    int nxt = 0;
    len[i] = (len[s[top - 1]] + a[i].x) % mod;
    if(top == 1)
        ans[i] = calc(len[i] - 1);
    else
    {
        ans[i] = (ans[i] + calc(min(mx[i][a[i].c],a[i].x))) % mod;
        pair<int,int> t = query(a[i].x,rt[i][a[i].c],1,X);
        ans[i] = (ans[i] + t.first) % mod,nxt = t.second;
        if(!nxt && a[i].c == a[s[1]].c && a[i].x > a[s[1]].x)
            nxt = 1,ans[i] = (ans[i] + (long long)a[s[1]].x * max(0,a[i].x - mx[i][a[i].c])) % mod;
    }
    mx[i][a[i].c] = max(mx[i][a[i].c],a[i].x),update(a[i].x,len[s[top - 1]],top,rt[i][a[i].c],1,X);
    for(register int j = first[i];j;j = pre[j])
        memcpy(mx[to[j]],mx[s[nxt + 1]],sizeof mx[to[j]]),memcpy(rt[to[j]],rt[s[nxt + 1]],sizeof rt[to[j]]),ans[to[j]] = ans[i],dfs(to[j]);
    --top;
}
int main()
{
    scanf("%d",&n);
    char op,c;
    int x;
    for(register int i = 1,cur = 0;i <= n;++i)
    {
        scanf(" %c%d",&op,&x);
        if(op == '1')
            scanf(" %c",&c),a[i].x = x,a[i].c = c - 'a',add(cur,i),cur = id[i] = i;
        else
            cur = id[i] = id[x];
    }
    for(register int i = first[0];i;i = pre[i])
        dfs(to[i]);
    for(register int i = 1;i <= n;++i)
        printf("%d\n",ans[id[i]]);
}