jzoj 4614. 【NOIP2016模拟7.12】字符串

Question

Solution

这题是道后缀数组的题目。
对于原串，我们先搞一遍后缀数组并求出$height$数组。
由于我用的是线段树，所以我们应当把询问按照a从大到小排个序。
线段树的叶子节点$i$表示$rank[i]$的位置，对于非叶子节点则维护其区间的最小值。（初始值为无穷大）
我们倒着枚举串中的位置，每到一个位置，便将它在线段树所在的位置赋值为在串中的位置。
如果当前的位置为某个询问的$a$，那么我们可以对其求出答案。
我们先二分答案，由于$rank$的一个性质：
对于两个后缀，如果其$rank$的差的绝对值越小，则其公共前缀长度越长。
所以我们可以对于该询问的$c$，求出其排名前后都与其公共前缀长度>=$mid$的范围。
可以用RMQ来求。
而后，我们可以在线段树里面查找该范围的最小值，
看是否有在$[a,b-mid+1]$这一段区间里面的数即可。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int t[N<<6];
struct num{int a,b,c,d,fr;}a[N];
int n,m,M,rk[N],tp[N],tax[N],sa[N];
int h[N],rt[N],tot=0,ma[N][17],out[N];
char s[N];

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

void qsort()
{
	for (int i=0;i<=M;i++) tax[i]=0;
	for (int i=1;i<=n;i++) tax[rk[i]]++;
	for (int i=1;i<=M;i++) tax[i]+=tax[i-1];
	for (int i=n;i>0;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}

void hzsz()
{
	scanf("%s",s+1);M=27;
	for (int i=1;i<=n;i++) rk[i]=s[i]-'a'+1,tp[i]=i;
	qsort();
	for (int w=1,p;p!=n;w<<=1,M=p)
	{
		p=0;
		for (int i=n-w+1;i<=n;i++) tp[++p]=i;
		for (int i=1;i<=n;i++)
			if (sa[i]>w) tp[++p]=sa[i]-w;
		qsort();
		memcpy(tp,rk,sizeof(rk));
		rk[sa[1]]=p=1;
		for (int i=2;i<=n;i++)
		{
			if (tp[sa[i-1]]!=tp[sa[i]] || tp[sa[i-1]+w]!=tp[sa[i]+w]) p++;
			rk[sa[i]]=p;
		}
	}
	for (int i=1,j,k=0;i<=n;i++)
	{
		if (k) k--;
		j=sa[rk[i]-1];
		while (s[i+k]==s[j+k]) k++;
		h[rk[i]]=k;
	}
}

inline int cmp(num a,num b) {return a.a<b.a;}

void RMQ()
{
	for (int i=1;i<=n;i++) ma[i][0]=h[i+1];
	for (int j=1;j<=16;j++)
		for (int i=1;i+(1<<j-1)<=n;i++)
				ma[i][j]=std::min(ma[i][j-1],ma[i+(1<<j-1)][j-1]);
}

void build(int x,int l,int r)
{
	t[x]=1010580540;
	if (l==r) return;
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}

void insert(int x,int l,int r,int f,int to)
{
	t[x]=min(t[x],to);
	if (l==r) return;
	int mid=l+r>>1;
	if (f<=mid) insert(x<<1,l,mid,f,to);
	else insert(x<<1|1,mid+1,r,f,to);
}

int getmin(int x,int l,int r,int fl,int fr)
{
	if (fl<=l && fr>=r) return t[x];
	int mid=l+r>>1,s=1010580540;
	if (fl<=mid) s=std::min(s,getmin(x<<1,l,mid,fl,fr));
	if (fr>mid) s=std::min(s,getmin(x<<1|1,mid+1,r,fl,fr));
	return s;
}

int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	n=read(),m=read();
	hzsz();RMQ();
	for (int i=1;i<=m;i++)
		a[i].a=read(),a[i].b=read(),a[i].c=read(),a[i].d=read(),a[i].fr=i;
	std::sort(a+1,a+m+1,cmp);
	build(1,1,n);
	for (int i=n,now=m,l,r,mid,le,ri;i!=0;i--)
	{
		insert(1,1,n,rk[i],i);
		while (a[now].a==i)
		{
			l=0,r=min(a[now].d-a[now].c+1,a[now].b-a[now].a+1);
			while (l<=r)
			{
				mid=l+r>>1;le=ri=rk[a[now].c];
				for (int i=16;i>=0;i--)
					if (le>=(1<<i) && ma[le-(1<<i)][i]>=mid) le-=(1<<i);
				for (int i=16;i>=0;i--)
					if (ri+(1<<i)<=n && ma[r][i]>=mid) ri+=(1<<i);
				if (getmin(1,1,n,le,ri)<=a[now].b-mid+1) l=mid+1;
				else r=mid-1;
			}
			out[a[now--].fr]=l-1;
		}
	}
	for(int i=1;i<=m;i++)
		printf("%d
",out[i]);
	return 0;
}