洛谷 P4094 [HEOI2016/TJOI2016]字符串

链接

P4094

题意

给出一个长为 \(n\) 的字符串 \(S\)。\(m\) 次询问，每次询问给出 \(a,b,c,d\)，求出 \(S_{a\sim b}\) 的所有子串与 \(S_{c\sim d}\) 的最大 LCP。

\(n,m\le 1\times 10^5,a\le b,c\le d,1\le a,b,c,d\le n\)

分析

首先，虽然题目中的要求是子串，但我们感觉到可以用后缀来求 LCP，最后只需要用长度卡一下 LCP 的长度。所以我们把 SA 跑出来。

注意到 \(S_{c\sim d}\) 只有一个串，所以我们从 \(S_{c\sim n}\) 这个后缀下手，在排序后的后缀中，我们注意到一个后缀与其他后缀的 LCP 是从自己向两边单调不增的。也就是说如果有一个确定的 LCP 长度，我们就可以在排序后的后缀中二分出一个 \(rk\) 区间，这个区间内的后缀与 \(S_{c\sim n}\) 的 LCP 都大于等于确定的值。这里二分区间需要用到 \(O(1)\) 求区间 \(\min\)，使用 ST 表。
于是我们想到二分答案，这样就可以确定出一个 \(rk\) 的区间，只要这个区间里存在合法的 \(S_{a\sim n} \sim S_{b\sim n}\)，就可以继续二分答案下去。
我们考虑怎样的 \(S_{a\sim n}\) 是合法的，首先 \(rk[a]\) 必须在我们得到的 \(rk\) 区间中。其次，\(S_{a\sim b}\) 也会有长度限制，如果我们当前二分的答案最长 LCP 是 \(mid\)，那么从 \([（b-mid+1）+1,b]\) 开始的后缀其实都不合法。
所以当我们得到了 \(rk\) 区间，我们就需要在 \([a,b-mid+1]\) 的后缀中统计是否存在 \(rk[i]\) 属于上述 \(rk\) 区间。问题转化为了区间查询值域的问题，使用主席树就可以解决。
至此时间复杂度 \(O(n\log^2 n)\)，可以通过本题。

算法

先跑出 SA 和 \(ht\) 的 ST 表。二分答案，判定答案时先二分出一个 \(rk\) 区间，然后主席树区间查询值域即可。

代码

#include
using namespace std;
#define in read()
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){p=p*10+c-'0';c=getchar();}
	return p*f;
}
const int N=100010;
string S;
int n,m,rk[N<<1],sa[N],height[N];
struct llmmkk{
	int fi,se,ref;
}st[N<<1],tmp[N<<1];
int cnt[N];
inline void jsort(){
	for(int i=0;i<=n;i++)cnt[i]=0;
	for(int i=1;i<=n;i++)cnt[st[i].se]++;
	for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>0;i--)tmp[cnt[st[i].se]]=st[i],cnt[st[i].se]--;	
	for(int i=0;i<=n;i++)cnt[i]=0;
	for(int i=1;i<=n;i++)cnt[tmp[i].fi]++;
	for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>0;i--)st[cnt[tmp[i].fi]]=tmp[i],cnt[tmp[i].fi]--;
}
int ston[257],t;
int lg2[N],minn[N][21];
inline void SA(){
	for(int i=0;i>1;
	lc[p]=newnode();built(l,mid,lc[p]);
	rc[p]=newnode();built(mid+1,r,rc[p]);
}
inline void newbuilt(int l,int r,int pre,int now,int x){
	lc[now]=lc[pre],rc[now]=rc[pre];
	if(l==r){sum[now]++;return ;}
	int mid=(l+r)>>1;
	if(x<=mid)newbuilt(l,mid,lc[pre],lc[now]=newnode(),x);
	else newbuilt(mid+1,r,rc[pre],rc[now]=newnode(),x);
	sum[now]=sum[lc[now]]+sum[rc[now]];
}
inline int query(int l,int r,int p,int ql,int qr){
	if(l>=ql&&r<=qr)return sum[p];
	int mid=(l+r)>>1,res=0;
	if(ql<=mid)res+=query(l,mid,lc[p],ql,qr);
	if(qr>mid)res+=query(mid+1,r,rc[p],ql,qr);
	return res;
}
inline bool check(int a,int b,int c,int mid){
	int tl,tr,l=1,r=c,md;while(l>1;if(getmin(md,c)>=mid)r=md-1;else l=md;}
	tl=l,l=c,r=n;while(l>1;if(getmin(c+1,md)>n>>m>>S;SA();
	built(1,n,rt[n+1]=newnode());
	for(int i=n;i>=1;i--)
		newbuilt(1,n,rt[i+1],rt[i]=newnode(),rk[i]);
	while(m--){
		int a=in,b=in,c=in,d=in;
		int l=0,r=d-c+1,mid;
		while(l>1;
			if(check(a,b,rk[c],mid))l=mid;
			else r=mid-1;
		}
		cout<