Loj #3055. 「HNOI2019」JOJO

JOJO 的奇幻冒险是一部非常火的漫画。漫画中的男主角经常喜欢连续喊很多的「欧拉」或者「木大」。

为了防止字太多挡住漫画内容，现在打算在新的漫画中用 \(x\) 欧拉或者 \(x\) 木大表示有 \(x\) 个欧拉或者木大。

为了简化内容我们现在用字母表示喊出的话。

我们用数字和字母来表示一个串，例如：2 a 3 b 表示的串就是 aabbb。

一开始漫画中什么话都没有，接下来你需要依次实现 \(n\) 个操作，总共只有 \(2\) 种操作：

• 第一种：1 x c：在当前漫画中加入 \(x\) 个 \(c\)，表示在当前串末尾加入 \(x\) 个 \(c\) 字符。保证当前串是空串或者串尾字符不是 \(c\)；
• 第二种：2 x：觉得漫画没画好，将漫画还原到第 \(x\) 次操作以后的样子，表示将串复原到第 \(x\) 次操作后的样子，如果 \(x=0\) 则是将串变成空串。如果当前串是 bbaabbb，第 \(4\) 次操作后串是 bb，则 2 4 会使 bbaabbb 变成 bb，保证 \(x\) 小于当前操作数。

众所周知空条承太郎十分聪明，现在迪奥已经被打败了，他开始考虑自己的漫画中的一些问题：

对于一个串的每个前缀 \(A\)，都有一个最长的比它短的前缀 \(B\) 与前缀 \(A\) 的一个后缀匹配，设这个最长的前缀 \(B\) 的长度为 \(L\)。\(L\) 为 \(0\) 时意味着 \(B\) 是一个空串。

每一次操作后，你都需要将当前的串的所有前缀的 \(L\) 求和并对 \(998244353\) 取模输出告诉空条承太郎，好和他的白金之星算出的答案对比。比如 bbaaabba 的 \(L\) 分别是 \(0, 1, 0, 0, 0, 1, 2, 3\)，所以对于这个串的答案就是 \(7\)。

输入格式

第一行包括一个正整数 \(n\)，表示操作数量。

接下来 \(n\) 行每行包含一个操作，操作格式如题目描述所示，例如：

• 1 x c
• 2 x

保证数据合法。

输出格式

仅包含 \(n\) 行，第 \(i\) 行一个整数，表示 \(i\) 个操作之后串的答案。

数据范围与提示

\(20\%\) 的数据满足 \(n\le 300\)，对于每个 \(1\) 操作中的 \(x\le 300\)；

另有 \(30\%\) 的数据满足 \(n\le 10^5\)，且对于每个 \(1\) 操作中的 \(x=1\)；

另有 \(30\%\) 的数据满足 \(n\le 10^5\)，且不含 \(2\) 操作；

\(100\%\) 的数据满足 \(n\le 10^5\)，且每个 \(1\) 操作中的 \(x\le 10^4\)。

我们用一个节点代表一次加入的一段连续字符。

假设每个加入的节点的父亲就是上一次加入的节点，这样我们就得到了一颗树。

计算答案的时候就在树上\(dfs\)并用可回退数据结构维护一下就行了。为了避免跳\(next\)的操作，我们可以用可持久化线段树维护儿子集合。

不过我计算答案也是暴力跳的。我想了个解决方案就是对每个\(next\)的链的每种字符维护一个栈就行了。

代码：

#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;

}