Wa on #2~#6 & #20

#include<bits/stdc++.h>
#define int long long
#define For(l,r,b) for(b=l;b<=r;b++)
#define N 600005
#define inf 1000000007ll
using namespace std;
string s;
int i,j,sa[N],rk[N],rk1[N],sec[N],tot[N],n,h[N];
int tr[N][2];
int a[N],A[N];
vector<int> hp[N];
struct tree{
	int l,r,s1,s2,b1,b2;
}t[4*N];
struct an{
	int s1,s2,b1,b2;
};
an mi(an x,an y)
{
	return {min(x.s1,y.s1),min(max(x.s1,y.s1),min(x.s2,y.s2)),max(x.b1,y.b1),max(min(x.b1,y.b1),max(x.b2,y.b2))};
}
void pushup(int o)
{
	an x={t[o*2].s1,t[o*2].s2,t[o*2].b1,t[o*2].b2},y={t[o*2+1].s1,t[o*2+1].s2,t[o*2+1].b1,t[o*2+1].b2};
	an xy=mi(x,y);
	t[o]={t[o].l,t[o].r,xy.s1,xy.s2,xy.b1,xy.b2};
}
set<int> se;
void build(int l,int r,int o)
{
	t[o].l=l;t[o].r=r;
	if(l==r)
	{
		t[o].s1=t[o].b1=A[l];
		t[o].s2=inf;
		t[o].b2=-inf;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o*2);
	build(mid+1,r,o*2+1);
	pushup(o);
}
an query(int l,int r,int o)
{
	if(t[o].l>=l&&t[o].r<=r) return {t[o].s1,t[o].s2,t[o].b1,t[o].b2};
	int mid=(t[o].l+t[o].r)>>1;
	an ans={inf,inf,-inf,-inf};
	if(l<=mid) ans=mi(ans,query(l,r,o*2));
	if(r>mid) ans=mi(ans,query(l,r,o*2+1));
	return ans;
}
void change(int x,int y,int id)
{
	x++;
	for(;x<=n;x+=x&-x) tr[x][id]=max(tr[x][id],y);
}
int ask(int x,int id)
{
	x++;
	int ans=-1;
	for(;x>0;x-=x&-x) ans=max(ans,tr[x][id]);
	return ans;
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0); 
	cin>>n>>s;
	For(1,n,i) cin>>a[i];
	s='#'+s;
	For(1,n,i) tot[s[i]]++,rk[i]=s[i];
	For(1,128,i) tot[i]+=tot[i-1];
	for(i=n;i;i--) sa[tot[rk[i]]--]=i;
	int sz=128;
	for(int k=1;k<=n;k<<=1)
	{
		int cnt=0;
		For(n-k+1,n,i) sec[++cnt]=i;
		For(1,n,i) if(sa[i]>k) sec[++cnt]=sa[i]-k;
		memset(tot+1,0,sz<<3);
		For(1,n,i) ++tot[rk[i]];
		For(1,sz,i) tot[i]+=tot[i-1];
		for(i=n;i>=1;i--) sa[tot[rk[sec[i]]]--]=sec[i];
		memcpy(rk1+1,rk+1,n<<3);
		sz=1;
		rk[sa[1]]=1;
		For(2,n,i) rk[sa[i]]=(rk1[sa[i]]==rk1[sa[i-1]]&&rk1[sa[i]+k]==rk1[sa[i-1]+k])?sz:++sz;
		if(sz==n) break;
	}
	For(1,n,i)
	{
		int pt=max(0ll,h[rk[i-1]]-1);
		while(s[i+pt]==s[sa[rk[i]-1]+pt]) pt++;
		h[rk[i]]=pt;
	}
	h[1]=0;
	For(1,n,i) A[i]=a[sa[i]];
	For(1,n,i) hp[h[i]].push_back(i);
	build(1,n,1);
	an as=query(1,n,1);
	change(1,1,0);change(0,0,1);
	long long ans=(n-1)*n/2,an2=max(as.b1*as.b2,as.s1*as.s2);
	se.insert(an2);
	cout<<ans<<" "<<an2<<endl;
	For(0,n-2,i)
	{
		for(auto j:hp[i])
		{
			int lf=ask(j-1,0),rf=n+1-ask(n-j,1);
			if(j==1) lf++;
			lf++,rf--;
			an gx;int gp;
			if(rf>=lf)
			{gx=query(lf-1,rf,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);se.erase(-gp);}
			ans-=(rf-lf+1)*(rf-lf+2)/2;
			ans+=(j+1-lf)*(j-lf)/2;
			ans+=(rf-j+1)*(rf-j)/2;
			if(j-1>=lf)
			{
				gx=query(lf-1,j-1,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
				if(gp!=inf*inf) se.insert(-gp);
			}
			if(j+1<=rf)
			{
				gx=query(j,rf,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
				if(gp!=inf*inf) se.insert(-gp);
			}
			change(j,j,0);change(n+1-j,n+1-j,1);
		}
		cout<<ans<<" "<<(ans==0?0:(-(*se.lower_bound(-inf*inf))))<<endl;
	}
	return 0;
}