首先显然往 KMP 想，但是好像没有限制总长诶那怎么办呢（
考虑把 \((x,c)\) 这个二元组看做一个字符。
求 Fail 的时候除了第一个二元组，别的二元组都要完全匹配。
因为如果仅是 \(c\) 相同而 \(x\) 不同，下一个字符一定匹配不上，没有什么用。
但是答案是需要这些贡献的。所以一个 Fail 应当造成一个等差数列的贡献。
诶但是有可持久化怎么办呢（
建个操作树递归处理（在线模拟这个也是可以的，只不过要把操作树上的链可持久化下来）。
诶但是 KMP 复杂度不是均摊的吗怎么办呢（
众所周知 AC 自动机暴力跳 Fail 复杂度是错的，所以我们的做法是直接把失配的边连向失配之后该跳到的状态。
KMP 也可以类似这样做，我们就得到了一个叫 KMP 自动机的东西。
然后主席树维护一下边和贡献就可以了（
具体地，注意到对于 \(i \le x\) 都有一个 \(l_i + i\) 的形式，其中 \(l_i\) 是 Fail 链上在此处深度最大的贡献。
\(i\) 拆出来直接算，\(l_i\) 可以用主席树区间赋值维护。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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]]);
}