BZOJ 4453 cys就是要拿英魂！（后缀数组+单调栈+平衡树）

一开始的时候感觉就是一个主席树裸题。

然后发现自己错了。

首先建出后缀数组。

设\(i<j\)

如果\(rk[i]>rk[j]\)显然i更优。

如果\(rk[i]<rk[j]\)不一定是j更优。

当\(i+lcp(i,j)-1<=j\)时是\(j\)优，否则\(i\)更优。

所以我们有一个初步的想法。离线之后把询问按右端点从小到大排序。

然后我们从1到n枚举，用平衡树维护当前可能的答案。

然后当平衡树某一个点\(i\)满足\(rk[i]<rk[j]\)且\(i+lcp(i,j)-1<=j\)时就把\(i\)从平衡树中删去。

询问时\(l\)的后继就是答案。

从这里就可以看出答案是成区间分布的。我们只需要关心什么时候当前最优的答案会改变。

具体的话我们可以维护一个递减的单调栈。当插入一个数时，把小于这个数rk的数弹出，并给弹出的数附一个从平衡树中删除的位置\(i+lcp(rk[stack[top]],rk[i])\)，并把i插入平衡树。当扫到这个点的时候把对应的数从平衡树中删掉就行了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

#include<cstdlib>

#include<ctime>

using namespace std;

const int N=101000;

vector<int> vec[N];

char s[N];

int c[N],x[N],n,m,y[N],sa[N],rk[N],height[N];

int mn[N][20];

int tot,rad[N],w[N],v[N],ch[N][2],root,X,Y,Z;

int top,stack[N],ans[N];

struct ques{

	int l,r,id;

}q[N];

bool cmp(ques a,ques b){

	return a.r<b.r;

}

void get_sa(){

	for(int i=1;i<=n;i++)c[x[i]=s[i]]++;

	for(int i=1;i<=m;i++)c[i]+=c[i-1];

	for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;

	for(int k=1;k<=n;k<<=1){

		int num=0;

		for(int i=n-k+1;i<=n;i++)y[++num]=i;

		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;

		for(int i=1;i<=m;i++)c[i]=0;

		for(int i=1;i<=n;i++)c[x[i]]++;

		for(int i=1;i<=m;i++)c[i]+=c[i-1];

		for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;

		for(int i=1;i<=n;i++)swap(x[i],y[i]);

		x[sa[1]]=1;num=1;

		for(int i=2;i<=n;i++)

			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;

		if(n==num)break;

		m=num;

	}

}

void get_height(){

	int k=0;

	for(int i=1;i<=n;i++)rk[sa[i]]=i;

	for(int i=1;i<=n;i++){

		if(rk[i]==1)continue;

		if(k)k--;

		int j=sa[rk[i]-1];

		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;

		height[rk[i]]=k;

	}

}

void pre_work(){

	for(int i=1;i<=n;i++)mn[i][0]=height[i];

	int len=log2(n);

	for(int j=1;j<=len;j++)

		for(int i=1;i+(1<<j)-1<=n;i++)

			mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);

}

int lcp(int l,int r){

	if(l>r)swap(l,r);

	l++;

	int len=log2(r-l+1);

	return min(mn[l][len],mn[r-(1<<len)+1][len]);

}

int new_node(int a,int b){

	int now=++tot;

	rad[now]=rand();v[now]=a;w[now]=b;

	return now;

}

int merge(int x,int y){

	if(!x||!y)return x+y;

	if(rad[x]>rad[y]){

		ch[x][1]=merge(ch[x][1],y);

		return x;

	}

	else{

		ch[y][0]=merge(x,ch[y][0]);

		return y;

	}

}

void split(int &x,int &y,int now,int k){

	if(now==0)x=y=0;

	else{

		if(v[now]<=k){

			x=now;

			split(ch[x][1],y,ch[x][1],k);

		}

		else{

			y=now;

			split(x,ch[y][0],ch[y][0],k);

		}

	}

}

int kth(int now,int k){

	if(ch[now][0])return kth(ch[now][0],k);

	return now;

}

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int main(){

	srand(time(NULL));

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

	n=strlen(s+1);

	m=2000;

	get_sa();

	get_height();

	pre_work();

	m=read();

	for(int i=1;i<=m;i++)

		q[i].l=read(),q[i].r=read(),q[i].id=i;

	sort(q+1,q+1+m,cmp);

	int now=1;

	for(int i=1;i<=n;i++){

		while(top&&rk[stack[top]]<rk[i])vec[i+lcp(rk[stack[top]],rk[i])].push_back(stack[top]),top--;

		stack[++top]=i;

		split(X,Y,root,i);

		root=merge(merge(X,new_node(i,rk[i])),Y);

		for(int j=0;j<vec[i].size();j++){

			split(X,Z,root,vec[i][j]);

			split(X,Y,X,vec[i][j]-1);

			root=merge(X,Z);

		}

		while(q[now].r==i){

			split(X,Y,root,q[now].l-1);

			ans[q[now].id]=v[kth(Y,1)];

			root=merge(X,Y);

			now++;

		}

	}

	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);

	return 0;

}

巴特西

BZOJ 4453 cys就是要拿英魂！（后缀数组+单调栈+平衡树）

最新文章

热门文章