WA on #18 95pts 求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1; 
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=6e5+10,inf=3e18+10;
ll sa[N<<1],rk[N<<1],ork[N<<1],id[N<<1],cnt[N],hei[N<<1];
ll n,a[N],val,rks;
vector<ll>v[N];
char c[N<<1];

ll f[N],ma[N],maa[N],mi[N],mii[N],siz[N];
ll sum,ans=-inf;

void init(){
	val=3e5;
	for(int i=1;i<=n;i++) rk[i]=c[i],cnt[rk[i]]++;
	for(int i=1;i<=val;i++) cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
	for(int i=1;i<=n;i++) ork[i]=rk[i];
	for(int i=1;i<=n;i++){
		if(ork[sa[i]]==ork[sa[i-1]]) rk[sa[i]]=rks;
		else rk[sa[i]]=++rks;
	}
	val=rks;
	for(int len=1;len<n;len<<=1){
		
		int pos=0;
		for(int i=n-len+1;i<=n;i++) id[++pos]=i;
		for(int i=1;i<=n;i++) if(sa[i]>len) id[++pos]=sa[i]-len;
		
		for(int i=0;i<=val;i++) cnt[i]=0;
		for(int i=1;i<=n;i++) cnt[rk[i]]++;
		for(int i=1;i<=val;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];
		
		rks=0;
		for(int i=1;i<=n;i++) ork[i]=rk[i];
		for(int i=1;i<=n;i++){
			if(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+len]==ork[sa[i-1]+len]) rk[sa[i]]=rks;
			else rk[sa[i]]=++rks;
		}
		val=rks;
		if(val>=n) break;
	}
	for(int i=1,j=0;i<=n;i++){
		if(j) j--;
		while(i+j<=n&&sa[rk[i]-1]+j<=n&&c[i+j]==c[sa[rk[i]-1]+j]) ++j;
		hei[rk[i]]=j;
	}
	for(int i=2;i<=n;i++) v[hei[i]].emplace_back(i);
//	for(int i=1;i<=n;i++) cout<<sa[i]<<" ";
//	cout<<"\n";	
//	for(int i=1;i<=n;i++) cout<<rk[i]<<" ";
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<<hei[i]<<" ";
//	cout<<"\n";
}
ll fin(ll x){
	return f[x]==x ? x : f[x]=fin(f[x]);
}
void mer(ll x,ll y){
	if((!f[x])||(!f[y])) return ;
	ll xx=fin(x),yy=fin(y);
	if(xx==yy) return ; 
	sum-=(siz[xx]-1)*siz[xx]/2+(siz[yy]-1)*siz[yy]/2; 
	siz[xx]+=siz[yy],f[yy]=xx;
	sum+=(siz[xx]-1)*siz[xx]/2; 
	if(ma[xx]<=ma[yy]) maa[xx]=max(ma[xx],maa[yy]),ma[xx]=ma[yy];
	else maa[xx]=max(maa[xx],ma[yy]);
	if(mi[xx]>=mi[yy]) mii[xx]=min(mi[xx],mii[yy]),mi[xx]=mi[yy];
	else mii[xx]=min(mii[xx],mi[yy]); 
	if(ma[xx]!=-(3e9)&&maa[xx]!=-(3e9)) ans=max(ans,ma[xx]*maa[xx]);
	if(mi[xx]!=(3e9)&&mii[xx]!=(3e9)) ans=max(ans,mi[xx]*mii[xx]);
}
ll sums[N],anss[N];
signed main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	read(n);
	scanf("%s",c+1);
	for(int i=1;i<=n;i++) read(a[i]);
	init();
	for(int i=1;i<=n;i++) ma[i]=maa[i]=-(3e9),mi[i]=mii[i]=(3e9);
	ll sumss=0;
	for(int i=n-1;i>=0;i--){
		for(ll p : v[i]){
			f[p]=p;
			if(f[p+1]==0){
//				sumss++;
				siz[p]++;
				if(a[sa[p]]>=ma[p]) maa[p]=ma[sa[p]],ma[p]=a[sa[p]];
				else maa[p]=max(maa[p],a[sa[p]]);
				if(a[sa[p]]<=mi[p]) mii[p]=mi[p],mi[p]=a[sa[p]];
				else mii[p]=min(mii[p],a[sa[p]]);
			}
			if(f[p-1]==0){
				siz[p]++;
//				sumss++;
				if(a[sa[p-1]]>=ma[p]) maa[p]=ma[p],ma[p]=a[sa[p-1]];
				else maa[p]=max(maa[p],a[sa[p-1]]);
				if(a[sa[p-1]]<=mi[p]) mii[p]=mi[p],mi[p]=a[sa[p-1]];
				else mii[p]=min(mii[p],a[sa[p-1]]);
			}
			sum+=(siz[p]-1)*siz[p]/2;
			if(ma[p]!=-(3e9)&&maa[p]!=-(3e9)) ans=max(ans,ma[p]*maa[p]);
			if(mi[p]!=(3e9)&&mii[p]!=(3e9)) ans=max(ans,mi[p]*mii[p]);
			if(f[p-1]) mer(p,p-1);
			if(f[p+1]) mer(p,p+1);
		}
		sums[i]=sum,anss[i]=(sum==0 ? 0 : ans);
	}
	for(int i=0;i<n;i++) write(sums[i]),putchar(' '),write(anss[i]),putchar('\n');
//	write(n),putchar('\n'),write(sumss);
	putchar('\n');
	return 0;
}
/*
如果两杯酒可以 k 相似，那么就可以 <=k 相似 

最大值大了？说明值合并的部分可能重复了一些

一个值被提取有两种可能：一个是 i+1被选中，一个是 i 被选中

当选中 p 时，需要考虑 p+1 是否被选中过，否则 p 不能选，p-1 则需要考虑 p-1 是否选中过，否则不能选 

现在问题时一些本不应该被合并的块我将他们合并成了一块，因此提前更新了最大值

 
*/