文件详细信息

下载本文件

本文件的大小为 3668 字节。

#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		bool flag=true;
		int ch=gc();
		num=0;
		while(ch<48||ch>57){
			if(ch=='-')flag=false;
			ch=gc();
		}
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
		flag||(num=-num);
	}
	int getstr(char*str){
		char ch=gc(),*tmp=str;
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t'&&ch!=EOF)*(str++)=ch,ch=gc();
		return str-tmp;
	}
	template<typename T>
	void write(T a){
		static int ch[20],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::getstr;
using IO::write;
typedef long long ll;
const int maxn=1000000;
template<typename T>
inline void chkmax(T&a,const T b){
	a<b&&(a=b);
}
template<typename T>
inline void chkmin(T&a,const T b){
	a>b&&(a=b);
}
int n,arr[maxn+1];
char s[maxn+2];
int sa[maxn+1],rk[maxn*2+1],oldrk[maxn*2+1],id[maxn+1],cnt[maxn+1],ht[maxn+1];
void initSA(const int n){
	int m=n>128?n:128;
	for(int i=1;i<=n;i++)++cnt[rk[i]=s[i]];
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;w<n;w<<=1){
		memset(cnt,0,sizeof(int)*(m+1));
		for(int i=1;i<=n;i++)++cnt[rk[(id[i]=sa[i])+w]];
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[id[i]+w]]--]=id[i];
		memset(cnt,0,sizeof(int)*(m+1));
		for(int i=1;i<=n;i++)++cnt[rk[id[i]=sa[i]]];
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[id[i]]]--]=id[i];
		memcpy(oldrk,rk,sizeof(int)*(n+1));
		int p=0;
		for(int i=1;i<=n;i++)
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		m=p;
		if(p==n)break;
	}
	for(int i=1,k=0;i<=n;i++){
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
		ht[rk[i]]=k;
	}
}
struct DSU{
	int fa[maxn+1],size[maxn+1],mx[maxn+1],mn[maxn+1];
	int find(const int x){
		return x==fa[x]?x:fa[x]=find(fa[x]);
	}
}dsu;
ll ans[maxn+1][2];
int main(){
	read(n);
	getstr(s+1);
	initSA(n);
	for(int i=1;i<=n;i++)read(arr[i]);
	for(int i=1;i<=n;i++)dsu.fa[i]=i;
	for(int i=1;i<=n;i++)dsu.size[i]=1;
	memcpy(dsu.mx+1,arr+1,sizeof(int)*n);
	memcpy(dsu.mn+1,arr+1,sizeof(int)*n);
	memset(cnt,0,sizeof(int)*(n+1));
	for(int i=1;i<=n;i++)++cnt[ht[i]];
	for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)id[cnt[ht[i]]--]=i;
	for(int i=0;i<=n;i++)ans[i][1]=-1000000000000000000ll;
	for(int i=n;i>=1;i--){
		const int u=id[i],x=dsu.find(sa[u-1]),y=dsu.find(sa[u]);
		if(!x||!y)continue;
		ans[ht[u]][0]+=(ll)dsu.size[x]*dsu.size[y];
		chkmax(ans[ht[u]][1],(ll)dsu.mx[x]*dsu.mx[y]);
		chkmax(ans[ht[u]][1],(ll)dsu.mn[x]*dsu.mn[y]);
		if(dsu.size[x]>dsu.size[y]){
			dsu.size[x]+=dsu.size[y];
			dsu.fa[y]=x;
			chkmax(dsu.mx[x],dsu.mx[y]);
			chkmin(dsu.mn[x],dsu.mn[y]);
		}else{
			dsu.size[y]+=dsu.size[x];
			dsu.fa[x]=y;
			chkmax(dsu.mx[y],dsu.mx[x]);
			chkmin(dsu.mn[y],dsu.mn[x]);
		}
	}
	for(int i=n;i>=1;i--){
		ans[i-1][0]+=ans[i][0];
		chkmax(ans[i-1][1],ans[i][1]);
	}
	for(int i=0;i<n;i++)write(ans[i][0]),pc(' '),write(ans[i][0]?ans[i][1]:0ll),pc('\n');
	return 0;
}