Loj #3055. 「HNOI2019」JOJO

JOJO 的奇幻冒險(xiǎn)是一部非?；鸬穆?。漫畫中的男主角經(jīng)常喜歡連續(xù)喊很多的「歐拉」或者「木大」。

為了防止字太多擋住漫畫內(nèi)容，現(xiàn)在打算在新的漫畫中用 \(x\) 歐拉或者 \(x\) 木大表示有 \(x\) 個(gè)歐拉或者木大。

為了簡(jiǎn)化內(nèi)容我們現(xiàn)在用字母表示喊出的話。

我們用數(shù)字和字母來(lái)表示一個(gè)串，例如：2 a 3 b 表示的串就是 aabbb。

一開始漫畫中什么話都沒有，接下來(lái)你需要依次實(shí)現(xiàn) \(n\) 個(gè)操作，總共只有 \(2\) 種操作：

• 第一種：1 x c：在當(dāng)前漫畫中加入 \(x\) 個(gè) \(c\)，表示在當(dāng)前串末尾加入 \(x\) 個(gè) \(c\) 字符。保證當(dāng)前串是空串或者串尾字符不是 \(c\)；
• 第二種：2 x：覺得漫畫沒畫好，將漫畫還原到第 \(x\) 次操作以后的樣子，表示將串復(fù)原到第 \(x\) 次操作后的樣子，如果 \(x=0\) 則是將串變成空串。如果當(dāng)前串是 bbaabbb，第 \(4\) 次操作后串是 bb，則 2 4 會(huì)使 bbaabbb 變成 bb，保證 \(x\) 小于當(dāng)前操作數(shù)。

眾所周知空條承太郎十分聰明，現(xiàn)在迪奧已經(jīng)被打敗了，他開始考慮自己的漫畫中的一些問(wèn)題：

對(duì)于一個(gè)串的每個(gè)前綴 \(A\)，都有一個(gè)最長(zhǎng)的比它短的前綴 \(B\) 與前綴 \(A\) 的一個(gè)后綴匹配，設(shè)這個(gè)最長(zhǎng)的前綴 \(B\) 的長(zhǎng)度為 \(L\)。\(L\) 為 \(0\) 時(shí)意味著 \(B\) 是一個(gè)空串。

每一次操作后，你都需要將當(dāng)前的串的所有前綴的 \(L\) 求和并對(duì) \(998244353\) 取模輸出告訴空條承太郎，好和他的白金之星算出的答案對(duì)比。比如 bbaaabba 的 \(L\) 分別是 \(0, 1, 0, 0, 0, 1, 2, 3\)，所以對(duì)于這個(gè)串的答案就是 \(7\)。

輸入格式

第一行包括一個(gè)正整數(shù) \(n\)，表示操作數(shù)量。

接下來(lái) \(n\) 行每行包含一個(gè)操作，操作格式如題目描述所示，例如：

• 1 x c
• 2 x

保證數(shù)據(jù)合法。

輸出格式

僅包含 \(n\) 行，第 \(i\) 行一個(gè)整數(shù)，表示 \(i\) 個(gè)操作之后串的答案。

數(shù)據(jù)范圍與提示

\(20\%\) 的數(shù)據(jù)滿足 \(n\le 300\)，對(duì)于每個(gè) \(1\) 操作中的 \(x\le 300\)；

另有 \(30\%\) 的數(shù)據(jù)滿足 \(n\le 10^5\)，且對(duì)于每個(gè) \(1\) 操作中的 \(x=1\)；

另有 \(30\%\) 的數(shù)據(jù)滿足 \(n\le 10^5\)，且不含 \(2\) 操作；

\(100\%\) 的數(shù)據(jù)滿足 \(n\le 10^5\)，且每個(gè) \(1\) 操作中的 \(x\le 10^4\)。

我們用一個(gè)節(jié)點(diǎn)代表一次加入的一段連續(xù)字符。

假設(shè)每個(gè)加入的節(jié)點(diǎn)的父親就是上一次加入的節(jié)點(diǎn)，這樣我們就得到了一顆樹。

計(jì)算答案的時(shí)候就在樹上\(dfs\)并用可回退數(shù)據(jù)結(jié)構(gòu)維護(hù)一下就行了。為了避免跳\(next\)的操作，我們可以用可持久化線段樹維護(hù)兒子集合。

不過(guò)我計(jì)算答案也是暴力跳的。我想了個(gè)解決方案就是對(duì)每個(gè)\(next\)的鏈的每種字符維護(hù)一個(gè)棧就行了。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define N 100005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=998244353;
int n;

const int maxx=1e4+1;
const int lx=1,rx=27*(1e4);
int rt[N];
vector<int>e[N];
int first[N];

int tag[N*70],ls[N*70],rs[N*70];
int tot;

void Insert(int &v,int old,int lx,int rx,int p,int ID) {
    v=++tot;
    ls[v]=ls[old];
    rs[v]=rs[old];
    if(lx==rx) {
        tag[v]=ID;
        return ;
    }
    int mid=lx+rx>>1;
    if(p<=mid) Insert(ls[v],ls[old],lx,mid,p,ID);
    else Insert(rs[v],rs[old],mid+1,rx,p,ID);
}

int query(int v,int lx,int rx,int p) {
    if(lx>p||rx<p) return 0;
    if(!v) return 0;
    if(lx==rx) return tag[v];
    int mid=lx+rx>>1;
    if(p<=mid) return query(ls[v],lx,mid,p);
    else return query(rs[v],mid+1,rx,p);
}

int fail[N];
int now=0;
int back[N],len[N],pre[N],col[N];
int sn[N];

ll Sum(ll n) {return n*(n+1)/2%mod;}

int cal(int v,int u) {
    int f=fail[v];
    ll ans=0;
    int lst=0;
    do {
        if(col[sn[f]]==col[u]) {
            if(!f) {
                if(min(len[sn[f]]-1,len[u])>lst) (ans+=Sum(min(len[sn[f]]-1,len[u]))-Sum(lst)+mod)%=mod;
                if(len[sn[f]]<=len[u]) (ans+=1ll*len[sn[f]]*(len[u]-max(lst,len[sn[f]]-1)))%=mod;
            } else if(len[sn[f]]>lst) {
                (ans+=1ll*(min(len[u],len[sn[f]])-lst)*pre[f])%=mod;
                lst=min(len[u],len[sn[f]]);
            }
        }
        f=fail[f];
    } while(f!=-1&&lst<len[u]);
    
    ans+=Sum(lst);
    return ans;
}

int cal2(int f,int u,int lim) {
    while(f!=-1) {
        if(col[sn[f]]==col[u]&&len[sn[f]]>=lim) return pre[f]+lim;
        f=fail[f];
    }
    f=0;
    return 0;
}

int ans[N];
int SN0;
void dfs1(int v) {
    for(int i=0;i<e[v].size();i++) {
        int to=e[v][i];
        int lst=query(rt[v],lx,rx,len[to]+col[to]*maxx);
        fail[to]=lst;
        Insert(rt[v],rt[v],lx,rx,len[to]+col[to]*maxx,to);
        if(!lst&&SN0&&col[SN0]==col[to]&&len[SN0]<=len[to]) fail[to]=SN0;
        rt[to]=rt[fail[to]];
        if(!v) SN0=to;
        dfs1(to);
        if(!v) SN0=0;
        Insert(rt[v],rt[v],lx,rx,len[to]+col[to]*maxx,lst);
    }
}

void dfs2(int v,ll tot) {
    ans[v]=tot;
    ll now;
    for(int i=0;i<e[v].size();i++) {
        int to=e[v][i];
        if(!v) now=(tot+Sum(len[to]-1))%mod;
        else {
            now=tot;
            (now+=cal(v,to))%=mod;
        }
        sn[v]=to;
        dfs2(to,now);
    }
}

int FA[N];
int qid[N];

int main() {
//  freopen("jojo10.in","r",stdin);
//  freopen("my.out","w",stdout);
    n=Get();
    int lst=0;
    int op,x;
    char c;
    int SN0=0;
    fail[0]=-1;
    first[0]=0;
    for(int i=1;i<=n;i++) {
        op=Get();
        if(op==1) {
            lst=back[i-1];
            rt[lst]=first[lst];
            x=Get();
            while(c=getchar(),!isalpha(c));
            len[++now]=x;
            pre[now]=pre[lst]+len[now];
            col[now]=c-'a';
            qid[i]=now;
            e[lst].push_back(now);
            FA[now]=lst;
            back[i]=now;
        } else {
            x=Get();
            back[i]=back[x];
            qid[i]=qid[x];
        }
    }
    dfs1(0);
    dfs2(0,0);
    for(int i=1;i<=n;i++) cout<<ans[qid[i]]<<"\n";
    return 0;
}