rt，蒟蒻按照自己的做法写了一个SAM上DP+线段树解法，正确性良好，但是会TLE 4个点？

求大佬卡常/纠错 qwq

// Problem: P2178 [NOI2015] 品酒大会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2178
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 1000010
int n,a[N];
char s[N];
map<int,int> ch[N];
vector<int> faln[N];
int tot=1,last=1;
int sz[N];
int fa[N],len[N],mx[N],mxp[N],mn[N],mnp[N];
int wsb[N];
void pd(int x){
	if(fa[x]){
		sz[fa[x]]+=sz[x];
		if(mx[fa[x]]<mx[x]){
			if(mx[fa[x]]>mxp[fa[x]]){
				mxp[fa[x]]=mx[fa[x]];
			}
			mx[fa[x]]=mx[x];
		}else if(mxp[fa[x]]<mx[x]){
			mxp[fa[x]]=mx[x];
		}
		if(mx[fa[x]]<mxp[x]){
			if(mx[fa[x]]>mxp[fa[x]]){
				mxp[fa[x]]=mx[fa[x]];
			}
			mx[fa[x]]=mxp[x];
		}else if(mxp[fa[x]]<mxp[x]){
			mxp[fa[x]]=mxp[x];
		}
		
		if(mn[fa[x]]>mn[x]){
			if(mn[fa[x]]<mnp[fa[x]]){
				mnp[fa[x]]=mn[fa[x]];
			}
			mn[fa[x]]=mn[x];
		}else if(mnp[fa[x]]>mn[x]){
			mnp[fa[x]]=mn[x];
		}
		if(mn[fa[x]]>mnp[x]){
			if(mn[fa[x]]<mnp[fa[x]]){
				mnp[fa[x]]=mn[fa[x]];
			}
			mn[fa[x]]=mnp[x];
		}else if(mnp[fa[x]]>mnp[x]){
			mnp[fa[x]]=mnp[x];
		}
	}
}
int iddr,itot;
void sam(int c){
	int p=last;
	int cur=++tot;
	len[cur]=len[p]+1;
	last=cur;
	for(;p&&!ch[p].count(c);p=fa[p]){
		ch[p][c]=cur;
	}
	if(!p){
		fa[cur]=1;
	}else{
		int q=ch[p][c];
		if(len[p]+1==len[q]){
			fa[cur]=q;
		}else{
			int cl=++tot;
			len[cl]=len[p]+1;
			for(auto [u,v]:ch[q]){
				ch[cl][u]=v;
			}
			fa[cl]=fa[q];
			fa[q]=fa[cur]=cl;
			for(;p;p=fa[p]){
				if(ch[p].count(c)&&ch[p][c]==q)
					ch[p][c]=cl;
			}
		}
	}
	sz[cur]++;mx[cur]=iddr;mn[cur]=iddr;
	wsb[++itot]=cur;
}
void dfs(int x){
	for(auto v:faln[x]){
		dfs(v);
	}
	pd(x);
}
int chafen[N];
vector<int> ans1l,ans2l;
int in[N<<2],tag[N<<2],tmpl[N];
void pushup(int x){
	in[x]=max(in[x<<1],in[x<<1|1]);
}
void pushdown(int x){
	if(tag[x]==-1e18)return;
	in[x<<1]=max(in[x<<1],tag[x]);
	in[x<<1|1]=max(in[x<<1|1],tag[x]);
	tag[x<<1]=max(tag[x<<1],tag[x]);
	tag[x<<1|1]=max(tag[x<<1|1],tag[x]);
	tag[x]=-1e18;
}
void edit(int x,int l,int r,int L,int R,int w){
	if(L<=l&&r<=R){
		tag[x]=max(tag[x],w);
		in[x]=max(in[x],w);
		return;
	}
	pushdown(x);
	int mid=l+r>>1;
	if(L<=mid)edit(x<<1,l,mid,L,R,w);
	if(R>mid)edit(x<<1|1,mid+1,r,L,R,w);
	pushup(x);
}
int qry(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return in[x];
	}
	pushdown(x);
	int mid=l+r>>1;
	int ret=-1e18;
	if(L<=mid)ret=max(ret,qry(x<<1,l,mid,L,R));
	if(R>mid)ret=max(ret,qry(x<<1|1,mid+1,r,L,R));
	return ret;
}
signed main(){
	ios::sync_with_stdio(0);
	rep(i,1,N-2)mx[i]=mxp[i]=-1e18,mn[i]=mnp[i]=1e18;
	rep(i,1,(N<<2)-2)in[i]=tag[i]=-1e18;
	cin>>n;
	scanf("%s",s+1);
	reverse(s+1,s+n+1);
	rep(i,1,n)cin>>a[i];
	reverse(a+1,a+n+1);
	rep(i,1,n)iddr=a[i],sam(s[i]-'a');
	rep(i,2,tot){
		faln[fa[i]].push_back(i);
	}
	dfs(1);
	rep(i,2,tot){
		int w=sz[i]*(sz[i]-1)/2;
		chafen[len[fa[i]]+1]+=w;
		chafen[len[i]+1]-=w;
	}
	int ans=0;
	ans1l.push_back(n*(n-1)/2);
	rep(i,1,n-1){
		ans+=chafen[i];
		ans1l.push_back(ans);
	}
	
	int answ=-1e18;
	
	answ=max(mn[1]*mnp[1],mx[1]*mxp[1]);
	ans2l.push_back(answ);
	rep(i,2,tot){
		if(mx[i]!=-1e18&&mxp[i]!=-1e18)edit(1,1,n,len[fa[i]]+1,len[i],mx[i]*mxp[i]);
		if(mn[i]!=1e18&&mnp[i]!=1e18)edit(1,1,n,len[fa[i]]+1,len[i],mn[i]*mnp[i]);
	}
	rep(i,1,n){
		ans2l.push_back((qry(1,1,n,i,i)==-1e18)?0:qry(1,1,n,i,i));
	}
	
	rep(i,0,n-1)cout<<ans1l[i]<<' '<<ans2l[i]<<'\n';
}