BZOJ 4199: [Noi2015]品酒大会/UOJ #131. 【NOI2015】品酒大会 后缀自动机 树形dp / 后缀数组 单调栈

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

typedef long long ll;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void print(ll x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=600100,inf=0X3f3f3f3f;
const ll Mn=-4485090715960753727;

int n;

struct SAM
{
	int trans[N][26],par[N],mx[N];
	int sz,root,suff;
	int size[N],V[N];
	bool book[N];
	int f[N][2];
	
	SAM(){sz=root=suff=1;}
	
	void insert(int x,int val)
	{
		int p=suff,np=++sz;
		size[np]=1;V[np]=val;book[np]=1;
		while(p && !trans[p][x])
			trans[p][x]=np,p=par[p];
		if(!p) par[np]=root;
		else
		{
			int q=trans[p][x];
			if(mx[q]==mx[p]+1) par[np]=q;
			else
			{
				int nq=++sz;
				mx[nq]=mx[p]+1;
				memcpy(trans[nq],trans[q],sizeof(trans[q]));
				par[nq]=par[q];
				par[q]=par[np]=nq;
				while(p && trans[p][x]==q)
					trans[p][x]=nq,p=par[p];
			}
		}
		suff=np;
	}
	
	void build(char *s,int *a)
	{
		register int i;
		for(i=1;i<=n;++i) insert(s[i]-'a',a[i]);
	}
	
	int last[N],ecnt;
	struct EDGE{int to,nt;}e[N];
	inline void add(int u,int v)
	{e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;}
	
	ll num[N],MX[N];
	
	void dp(int u)
	{
		if(book[u]) f[u][0]=f[u][1]=V[u];
		for(int i=last[u],v;i;i=e[i].nt)
		{
			v=e[i].to;
			dp(v);
			num[mx[u]]+=1ll*size[u]*size[v];
			size[u]+=size[v];
			
			if(f[v][0]!=inf)
			{
				if(f[u][0]!=inf)
					MX[mx[u]]=max(MX[mx[u]],1ll*f[u][0]*f[v][0]),
					MX[mx[u]]=max(MX[mx[u]],1ll*f[u][1]*f[v][1]),
					MX[mx[u]]=max(MX[mx[u]],1ll*f[u][0]*f[v][1]),
					MX[mx[u]]=max(MX[mx[u]],1ll*f[u][1]*f[v][0]),
					f[u][0]=max(f[u][0],f[v][0]),
					f[u][1]=min(f[u][1],f[v][1]);
				else f[u][0]=f[v][0],f[u][1]=f[v][1];
			}
		}
	}
	
	void solve()
	{
		register int i;
		for(i=2;i<=sz;++i)
			add(par[i],i);
		memset(f,0X3f,sizeof(f));
		memset(MX,-0X3f,sizeof(MX));
		dp(root);
		i=n;
		while(~(i--)) num[i]+=num[i+1];
		i=n;
		while(~i && MX[i+1]==Mn) MX[i+1]=0,i--;
		while(~i) MX[i]=max(MX[i],MX[i+1]),i--;
		
		for(i=0;i<n;++i)
			print(num[i]),putchar(' '),print(MX[i]),putchar('\n');
	}
}sam;

int a[N];
char s[N];

int main()
{
	n=read();
	scanf("%s",s+1);
	register int i;
	for(i=1;i<=n;++i) a[i]=read();
	if(n==1){puts("0 0");return 0;}
	reverse(s+1,s+1+n);
	reverse(a+1,a+1+n);
	sam.build(s,a);
	sam.solve();
	return 0;
}