uoj 131/bzoj 4199 [NOI2015]品酒大会后缀树+树d

题目大意

分析

题目的提示还是很明显的

\(r\)相似就就代表了\(0...r-1\)相似

建出后缀树我们能dfs算出答案

再后缀和更新一下即可

注意

细节挺多的，但数据很良心

不然我就狂wa不止了

LL,权值有负等等

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <cmath>

using namespace std;

const int M=600007;

typedef long long LL;

const LL INF=1e9+7;

const LL oo=9223372036854775807;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n;

char s[M];

int val[M];

int ch[M][26];

int fa[M],stp[M];

int right[M];

int last,tot;

LL sz[M],mx[M],mn[M];

LL ans1[M],ans2[M];

struct edge{int y,nxt;};

struct vec{

	int g[M],te;

	edge e[M];

	vec(){memset(g,0,sizeof(g));te=0;}

	void clear(){memset(g,0,sizeof(g));te=0;}

	inline void push(int x,int y){e[++te].y=y;e[te].nxt=g[x];g[x]=te;}

	inline int& operator () (int &x){return g[x];}

	inline edge& operator [] (int &x){return e[x];}

}go;

int newnode(int ss){

	stp[++tot]=ss;

	return tot;

}

int ext(int p,int q,int d){

	int nq=newnode(stp[p]+1);

	fa[nq]=fa[q]; fa[q]=nq;

	memcpy(ch[nq],ch[q],sizeof(ch[q]));

	for(;p&&ch[p][d]==q;p=fa[p]) ch[p][d]=nq;

	return nq;

}

int sam(int p,int d){

	int np=ch[p][d];

	if(np) return (stp[p]+1==stp[p]) ? np : ext(p,np,d);

	np=newnode(stp[p]+1);

	for(;p&&!ch[p][d];p=fa[p]) ch[p][d]=np;

	if(!p) fa[np]=1;

	else{

		int q=ch[p][d];

		fa[np]= (stp[p]+1==stp[q]) ? q :ext(p,q,d);

	}

	return np;

}

void dfs(int x){

	sz[x]=(right[x]>0);

	mx[x]=(right[x]>0)?val[right[x]]:-INF;

	mn[x]=(right[x]>0)?val[right[x]]:INF;

	int p,y;

	LL tp=0,secmx=-INF,secmn=INF;

	for(p=go(x);p;p=go[p].nxt){

		y=go[p].y;

		dfs(y);

		tp+=sz[x]*sz[y];

		if(mx[y]>=mx[x]) secmx=mx[x],mx[x]=mx[y];

		else if(mx[y]>secmx) secmx=mx[y];

		if(mn[y]<=mn[x]) secmn=mn[x],mn[x]=mn[y];

		else if(mn[y]<secmn) secmn=mn[y];

		sz[x]+=sz[y];

	}

	if(tp){

		int d=stp[x];

		ans1[d]+=tp;

		ans2[d]=max(ans2[d],mx[x]*secmx);

		ans2[d]=max(ans2[d],mn[x]*secmn);

	}

}

int main(){

	int i;

	n=rd();

	scanf("%s",s+1);

	for(i=1;i<=n;i++) val[i]=rd();

	last=tot=1;

	for(i=n;i>0;i--){

		last=sam(last,s[i]-'a');

		right[last]=i;

	}

	for(i=2;i<=tot;i++) go.push(fa[i],i);

	for(i=0;i<=n;i++) ans2[i]=-oo;

	dfs(1);

	for(i=n-1;i>=0;i--){

		ans1[i]+=ans1[i+1];

		ans2[i]=max(ans2[i],ans2[i+1]);

	}

	for(i=n-1;i>=0;i--) if(ans1[i]==0) ans2[i]=0;

	for(i=0;i<n;i++) printf("%lld %lld\n",ans1[i],ans2[i]);

	return 0;

}

巴特西

uoj 131/bzoj 4199 [NOI2015]品酒大会后缀树+树d

题目大意

分析

注意

solution

最新文章

热门文章

巴特西

uoj 131/bzoj 4199 [NOI2015]品酒大会 后缀树+树d

题目大意

分析

注意

solution

最新文章

热门文章

uoj 131/bzoj 4199 [NOI2015]品酒大会后缀树+树d