JOJO

求赞TwT（刷结题仙人awa）

#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
typedef pair<int, pair<int, long long> > lzt;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

inline char gc() {
    char c = getchar();
    while (c < 'a' || c > 'z') c = getchar();
    return c;
}

const int maxn = 100005, M = 1e4 + 7, mod = 998244353;

int n;
int val[maxn], pos[maxn], ans[maxn], a[maxn], b[maxn], top;
vector<int> to[maxn];

int rt[maxn][26], mx[maxn][26], tot;
struct seg
{
    int l, r, lch, rch, sum, lzy, nxt;
} t[maxn * 60];

#define mid ((l + r) >> 1)

inline void new_node(int &s) {t[++tot] = t[s]; s = tot;}
inline void add(int s, int v, int len) {t[s].sum = (ll)v * len % mod; t[s].lzy = v;}
inline void push_down(int s, int l, int r)
{
    if (!t[s].lzy) return ;
    new_node(t[s].lch); add(t[s].lch, t[s].lzy, mid - l + 1);
    new_node(t[s].rch); add(t[s].rch, t[s].lzy, r - mid);
    t[s].lzy = 0;
}

void modify(int &s, int l, int r, int x, int v, int p)
{
    new_node(s);
    if (r < x) return add(s, v, r - l + 1);
    if (l == r) return t[s].nxt = p, add(s, v, 1);
    push_down(s, l, r);
    modify(t[s].lch, l, mid, x, v, p);
    if (x > mid) modify(t[s].rch, mid + 1, r, x, v, p);
    t[s].sum = (t[t[s].lch].sum + t[t[s].rch].sum) % mod;
}

void query(int &s, int l, int r, int x, int &ans, int &nxt)
{
    if (r < x) return ans = (ans + t[s].sum) % mod, void();
    if (l == r) return ans = (ans + t[s].sum) % mod, nxt = t[s].nxt, void();
    push_down(s, l, r);
    query(t[s].lch, l, mid, x, ans, nxt);
    if (x > mid) query(t[s].rch, mid + 1, r, x, ans, nxt);
}

inline int getsum(int x) {return ((ll)x * (x + 1) >> 1) % mod;}

void dfs(int u)
{
    ++top;
    int x = val[u] / M, y = val[u] % M, nxt = 0;
    a[top] = val[u]; b[top] = b[top - 1] + y;
    if (top == 1) ans[u] = getsum(y - 1);
    else {
        ans[u] = (ans[u] + getsum(min(mx[top][x], y))) % mod;
        query(rt[top][x], 1, M, y, ans[u], nxt);
        if (!nxt && a[1] / M == x && b[1] < y) nxt = 1, ans[u] = (ans[u] + (ll)b[1] * max(0, y - mx[top][x])) % mod;
    }
    mx[top][x] = max(mx[top][x], y);
    modify(rt[top][x], 1, M, y, b[top - 1], top);
    for (int i=0;i<to[u].size();i++) {
    	int v = to[u][i];
        memcpy(mx[top + 1], mx[nxt + 1], sizeof(mx[top + 1]));
        memcpy(rt[top + 1], rt[nxt + 1], sizeof(rt[top + 1]));
        ans[v] = ans[u]; dfs(v);
    }
    --top;
}

void work() {
    n = read();
    for (int op, x, i = 1; i <= n; ++i) {
        op = read(); x = read();
        if (op == 1) val[++tot] = (gc() - 'a') * M + x, pos[i] = tot, to[pos[i - 1]].push_back(pos[i]);
        else pos[i] = pos[x];
    }

    for (int _ = 0; _ < to[0].size(); _++) {
    	int i = to[0][_];
        tot = 0;
        memset(rt[1], 0, sizeof(rt[1]));
        memset(mx[1], 0, sizeof(mx[1]));
        dfs(i);
    }

    for (int i = 1; i <= n; ++i) printf("%d\n", ans[pos[i]]);
}

int main(){
    #ifdef LZT
        freopen("in","r",stdin);
    #endif

    work();

    #ifdef LZT
        Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
    #endif
}