【BZOJ4199】品酒大会

    构造出后缀数组，算出height数组，按height从大到小排序，依次用并查集合并。

    我维护了正、负的最大、次大、最小值，不知道他们只维护最大值是怎么弄的...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=300010;
const LL inf=~0ull>>1;

char s[maxn];
LL a[maxn];
int sa[maxn],rank[maxn],h[maxn];
LL ansa[maxn],ansb[maxn];
int n;

int c[maxn],temp1[maxn],temp2[maxn];

void Build_SA()
{
	int i,m=128,*x=temp1,*y=temp2;
	for (i=0;i<=m;i++) c[i]=0;
	for (i=1;i<=n;i++) c[x[i]=s[i]]++;
	for (i=1;i<=m;i++) c[i]+=c[i-1];
	for (i=n;i;i--) sa[c[x[i]]--]=i;
	for (int k=1;k<=n;k<<=1)
	{
		int p=0;
		for (i=n-k+1;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k; 
		for (i=0;i<=m;i++) c[i]=0;
		for (i=1;i<=n;i++) c[x[y[i]]]++;
		for (i=1;i<=m;i++) c[i]+=c[i-1];
		for (i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);p=1;x[sa[1]]=p;
		for (i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
		if (p>=n) break;
		m=p;
	}
}

void Get_Height()
{
	for (int i=1;i<=n;i++) rank[sa[i]]=i;
	for (int i=1,x=0;i<=n;i++)
	{
		if (x) x--;
		int j=sa[rank[i]-1];
		while (i+x<=n && j+x<=n && s[i+x]==s[j+x]) x++;
		h[rank[i]]=x;
	}
}

struct Info {int id,h;}I[maxn];
bool cmp(const Info &a,const Info &b) {return a.h>b.h;}

LL submax1[maxn],submax2[maxn],negmax1[maxn],negmax2[maxn],submin[maxn],negmin[maxn],tot[maxn];
int f[maxn];

int Find(int x) {return f[x]==x?x:f[x]=Find(f[x]);}

void Update(int x,int y,int o)
{
	int fx=Find(x),fy=Find(y);
	f[fx]=fy;
	ansa[o]-=tot[fx]*(tot[fx]-1)/2;
	ansa[o]-=tot[fy]*(tot[fy]-1)/2;
	tot[fy]+=tot[fx];
	ansa[o]+=tot[fy]*(tot[fy]-1)/2;
	
	LL v1=submax1[fx],v2=submax1[fy],v3=submax2[fx],v4=submax2[fy];
	if (v1>v2) submax1[fy]=v1,submax2[fy]=max(v2,max(v3,v4));
		else   submax1[fy]=v2,submax2[fy]=max(v1,max(v3,v4));

	v1=negmax1[fx],v2=negmax1[fy],v3=negmax2[fx],v4=negmax2[fy];
	if (v1<v2) negmax1[fy]=v1,negmax2[fy]=min(v2,min(v3,v4));
		else   negmax1[fy]=v2,negmax2[fy]=min(v1,min(v3,v4));
		
	submin[fy]=min(submin[fy],submin[fx]);
	negmin[fy]=max(negmin[fy],negmin[fx]);
	
	if (submax1[fy]!=-inf && submax2[fy]!=-inf && ansb[o]<submax1[fy]*submax2[fy]) ansb[o]=submax1[fy]*submax2[fy];
	if (negmax1[fy]!=inf  && negmax2[fy]!=inf  && ansb[o]<negmax1[fy]*negmax2[fy]) ansb[o]=negmax1[fy]*negmax2[fy];
	if (submin[fy]!=inf   && negmin[fy]!=-inf  && ansb[o]<submin[fy]*negmin[fy]) ansb[o]=submin[fy]*negmin[fy];
}

void Init()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	Build_SA();
	Get_Height();
}

void Work()
{
	for (int i=0;i<=n;i++)
	{
		I[i].id=i;
		I[i].h=h[i];
		f[i]=i;
		submax1[i]=submax2[i]=negmin[i]=-inf;
		negmax1[i]=negmax2[i]=submin[i]=inf;
		if (i) if (a[i]>0) submax1[i]=submin[i]=a[i];else negmax1[i]=negmin[i]=a[i];
		tot[i]=1;
		ansb[i]=-inf;
	}
	tot[0]=0;
	ansb[n+1]=-inf;
	sort(I+1,I+1+n,cmp);
	for (int i=n,w=1;i>=0;i--)
	{
		ansa[i]=ansa[i+1];
		ansb[i]=ansb[i+1];
		while (w<=n && I[w].h==i)
			Update(sa[I[w].id-1],sa[I[w].id],i),w++;
	}
}

void Print()
{
	for (int i=0;i<n;i++)
	if (ansa[i]) printf("%lld %lld\n",ansa[i],ansb[i]);
		else printf("0 0\n");
}

int main()
{
	Init();
	Work();
	Print();
	return 0;
}