「NOI2015」品酒大会 - 后缀自动机

题目大意

---

题目分析

直接对原串建立后缀自动机。
统计每个结点的$end$-$pos$集合大小，$end$-$pos$集合中最大权，$end$-$pos$集合中最小权（负负得正）。
按照逆拓扑序维护每个结点的答案。
对于新产生的$r$相似的方法数即为：
$cnt[\left|max(now)\right|]+=C_{end\text{-}pos(now)}^2$
对于新产生的答案为：
$ans[\left|max(now)\right|]=\max\lbrace ans[\left|max(now)\right|],end$-$max[now][0]\times end$-$max[now][1],end$-$min[now][0]\times end$-$min[now][1])\rbrace$

但是$r+v(v\ge0)$都可以算作$r$相似。
此时我们对方法数做一个差分，然后对方法数和答案求前缀和即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=300005,maxc=26;

int n;
LL cnt[maxn],ans[maxn];

struct SuffixAutomaton {
	int size,root,last;
	int next[maxn*2],top[maxn*2],Bucket[maxn*2];
	LL Max[maxn*2],end_pos[maxn*2],end_max[maxn*2][2],end_min[maxn*2][2];
	int child[maxn*2][maxc];
	SuffixAutomaton() {
		size=0;
		root=last=newnode(0);
		for(int i=0; i<maxn*2; i++) {
			end_max[i][0]=end_max[i][1]=-LLONG_MAX;
			end_min[i][0]=end_min[i][1]=LLONG_MAX;
		}
	}
	int newnode(int len) {
		size++;
		next[size]=0;
		Max[size]=len;
		memset(child[size],0,sizeof(child[size]));
		return size;
	}
	void insert(int data,LL v) {
		int p=last,u=newnode(Max[last]+1);
		last=u;
		end_pos[u]=1;
		end_max[u][0]=end_min[u][0]=v;
		for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
		if(!p)next[u]=root;
		else {
			int old=child[p][data];
			if(Max[old]==Max[p]+1)next[u]=old;
			else {
				int New=newnode(Max[p]+1);
				copy(child[old],child[old]+maxc,child[New]);
				next[New]=next[old];
				next[u]=next[old]=New;
				for(; child[p][data]==old; p=next[p])child[p][data]=New;
			}
		}
	}
	void update_max(int index,LL v) {
		if(v>end_max[index][0]) {
			end_max[index][1]=end_max[index][0];
			end_max[index][0]=v;
		} else if(v>end_max[index][1])end_max[index][1]=v;
	}
	void update_min(int index,LL v) {
		if(v<end_min[index][0]) {
			end_min[index][1]=end_min[index][0];
			end_min[index][0]=v;
		} else if(v<end_min[index][1])end_min[index][1]=v;
	}
	void topsort() {
		for(int i=1; i<=size; i++)Bucket[Max[i]]++;
		for(int i=1; i<=size; i++)Bucket[i]+=Bucket[i-1];
		for(int i=1; i<=size; i++)top[Bucket[Max[i]]--]=i;
	}
	void run() {
		topsort();
		for(int i=0; i<=n+1; i++)ans[i]=-LLONG_MAX;
		for(int i=size; i>=1; i--) {
			int now=top[i];
			if(end_pos[now]>1) {
				cnt[Max[now]]+=(end_pos[now]-1)*end_pos[now]/2; //差分
				if(i!=1)cnt[Max[next[now]]]-=(end_pos[now]-1)*end_pos[now]/2;
				ans[Max[now]]=max(ans[Max[now]],max(end_max[now][0]*end_max[now][1],end_min[now][0]*end_min[now][1]));
			}
			if(i!=1) { //维护end-pos
				end_pos[next[now]]+=end_pos[now];
				update_max(next[now],end_max[now][0]);
				update_max(next[now],end_max[now][1]);
				update_min(next[now],end_min[now][0]);
				update_min(next[now],end_min[now][1]);
			}
		}
		for(int i=n; i>=0; i--)cnt[i]+=cnt[i+1];
		for(int i=n; i>=0; i--)ans[i]=max(ans[i],ans[i+1]);
		for(int i=0; i<=n; i++)
			if(ans[i]==-LLONG_MAX)ans[i]=0;
	}
} sam;

char s[maxn];
int a[maxn];

int main() {
	n=Get_Int();
	scanf("%s",s+1);
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=n; i>=1; i--)sam.insert(s[i]-'a',a[i]);
	sam.run();
	for(int i=0; i<n; i++)printf("%lld %lld\n",cnt[i],ans[i]);
	return 0;
}