[LOJ6198] 谢特

之乎者助得甚？

给定字符串(s)和序列(w)，试求

[max_{1le i<jle n} lcp(i,j)+(w_iveebar w_j) ]

似乎这样的东西都能很好的用SA(height)+启发式合并来完成？

可以联系这题思考。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,w[N],sa[N],ht[N],rc[N];
char s[N];

void buildSa() {
	static int c[N];
	int i,p,k,m=128,*x=ht,*y=rc;
	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>=1; --i) sa[c[x[i]]--]=i;
	for(k=1; k<n; k<<=1) {
		for(i=n-k+1,p=0; i<=n; ++i) y[++p]=i;
		for(i=1; i<=n; ++i) if(sa[i]>k) y[++p]=sa[i]-k;
		for(i=1; 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>=1; --i) sa[c[x[y[i]]]--]=y[i];
		swap(x,y), x[sa[1]]=p=1;
		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((m=p)>=n) break;
	}
	for(i=1; i<=n; ++i) rc[sa[i]]=i;
	for(i=1,k=0; i<=n; ++i) {
		p=sa[rc[i]-1]; if(k) k--; 
		while(s[p+k]==s[i+k]) k++;
		ht[rc[i]]=k;
	}
}

int tot,top,stk[N*18];
int ll[N],rr[N],bl[N],siz[N],ch[N*18][2];
pair<int,int> h[N];

int newNode() {
	return top?stk[top--]:++tot;
}
void fuckNode(int x) {
	stk[++top]=x; 
	ch[x][0]=ch[x][1]=0;
}
void insert(int x,int w) {
	for(int i=16; ~i; --i) {
		if(!ch[x][(w>>i)&1]) ch[x][(w>>i)&1]=newNode();
		x=ch[x][(w>>i)&1];
	}
}
int ans,tmp;
void query(int x,int y,int d,int now) {
	if(d<0) {
		tmp=max(tmp,now);
		return;
	}
	for(int k=0; k<2; ++k) if(ch[x][k]) {
		if(ch[y][k^1]) query(ch[x][k],ch[y][k^1],d-1,now|(1<<d));
		else query(ch[x][k],ch[y][k],d-1,now);
	}
}
void merge(int x,int y,int d) {
	if(d<0) return;
	for(int k=0; k<2; ++k) if(ch[x][k]) {
		if(!ch[y][k]) ch[y][k]=newNode();
		merge(ch[x][k],ch[y][k],d-1);
		fuckNode(ch[x][k]);
	}
}

int main() {
//	freopen("C:/Users/HSY/Downloads/2.in","r",stdin);
	
	scanf("%d%s",&n,s+1);
	for(int i=1; i<=n; ++i) 
		scanf("%d",w+i),newNode();
	buildSa();
	for(int i=2; i<=n; ++i) h[i-1]=make_pair(-ht[i],i);
	for(int i=1; i<=n; ++i) {
		ll[i]=rr[i]=bl[i]=i; siz[i]=1;
		insert(i,w[sa[i]]);
	}
	sort(h+1,h+n);
	for(int i=1; i<n; ++i) {
		int len=-h[i].first;
		int x=bl[h[i].second];
		int y=bl[h[i].second-1];
		if(siz[x]>siz[y]) swap(x,y);
		tmp=0; 
		query(x,y,16,0);
		ans=max(ans,tmp+len);
		for(int j=ll[x]; j<=rr[x]; ++j) bl[j]=y;
		ll[y]=min(ll[x],ll[y]);
		rr[y]=max(rr[x],rr[y]);
		siz[y]+=siz[x];
		merge(x,y,16);
	}
	printf("%d
",ans);
	return 0;
}