![BZOJ4556:[TJOI\HEOI2016]字符串(后缀数组,主席树,二分,ST表)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "BZOJ4556:[TJOI\HEOI2016]字符串(后缀数组,主席树,二分,ST表)")
Description
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？
Input
输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。1<=n,m<=100,000,
字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n
Output
对于每一次询问，输出答案。
Sample Input
5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4
Sample Output
1
1
2
2
2
1
2
2
2
Solution
设$suf_i$表示后缀$i$，
首先考虑二分一个答案$mid$，那么现在问题转化成求$suf_a$到$suf_{b-mid+1}$的这些个后缀中，是否有一个后缀和$suf(c)$的$lcp$大于等于$mid$。
设$SA_i$表示后缀排序排名为$i$的后缀，$Rank_i$表示$suf_i$的后缀排序排名。
由于对于$suf_c$，我们可以用二分+$ST$表求出后缀排序中的可行区间，可行区间内的后缀和$suc_c$的$lcp$长度都大于等于$mid$。现在问题转化为了求$suf_a$到$suf_{b-mid+1}$的这些后缀是否哪个后缀的$Rank$值在可行区间内，这个用一个主席树就好了。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#define N (100009)
using namespace std; struct Sgt{int ls,rs,val;}Segt[N*];
int Root[N],sgt_num;
int n,q,m=,a,b,c,d;
int ST[N][],LOG2[N];
int wa[N],wb[N],wt[N],SA[N],Height[N],Rank[N];
char r[N]; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} bool cmp(int *y,int a,int b,int k)
{
int arank1=y[a];
int brank1=y[b];
int arank2=a+k>=n?-:y[a+k];
int brank2=b+k>=n?-:y[b+k];
return arank1==brank1 && arank2==brank2;
} void Build_SA()
{
int *x=wa,*y=wb;
for (int i=; i<m; ++i) wt[i]=;
for (int i=; i<n; ++i) ++wt[x[i]=r[i]-'a'];
for (int i=; i<m; ++i) wt[i]+=wt[i-];
for (int i=n-; i>=; --i) SA[--wt[x[i]]]=i; for (int j=; j<=n; j<<=)
{
int p=;
for (int i=n-j; i<n; ++i) y[p++]=i;
for (int i=; i<n; ++i) if (SA[i]>=j) y[p++]=SA[i]-j; for (int i=; i<m; ++i) wt[i]=;
for (int i=; i<n; ++i) ++wt[x[y[i]]];
for (int i=; i<m; ++i) wt[i]+=wt[i-];
for (int i=n-; i>=; --i) SA[--wt[x[y[i]]]]=y[i]; m=; swap(x,y);
x[SA[]]=;
for (int i=; i<n; ++i)
x[SA[i]]=cmp(y,SA[i],SA[i-],j)?m-:m++;
if (m>=n) break;
}
} void Build_Height()
{
for (int i=; i<n; ++i) Rank[SA[i]]=i;
int k=;
for (int i=; i<n; ++i)
{
if (!Rank[i]) continue;
if (k) k--;
int j=SA[Rank[i]-];
while (r[i+k]==r[j+k]) ++k;
Height[Rank[i]]=k;
}
} void Build_ST()
{
for (int i=; i<=n; ++i) LOG2[i]=LOG2[i>>]+;
for (int i=; i<n; ++i) ST[i][]=Height[i];
for (int j=; j<=; ++j)
for (int i=; i+(<<j)-<n; ++i)
ST[i][j]=min(ST[i][j-],ST[i+(<<j-)][j-]);
} int Query(int l,int r)
{
int k=LOG2[r-l+];
return min(ST[l][k],ST[r-(<<k)+][k]);
} int Update(int pre,int l,int r,int x)
{
int now=++sgt_num;
Segt[now]=Segt[pre];
Segt[now].val++;
if (l==r) return now;
int mid=(l+r)>>;
if (x<=mid) Segt[now].ls=Update(Segt[now].ls,l,mid,x);
else Segt[now].rs=Update(Segt[now].rs,mid+,r,x);
return now;
} int Query(int u,int v,int l,int r,int l1,int r1)
{
if (l>r1 || r<l1) return ;
if (l1<=l && r<=r1) return Segt[v].val-Segt[u].val;
int mid=(l+r)>>;
return Query(Segt[u].ls,Segt[v].ls,l,mid,l1,r1)+Query(Segt[u].rs,Segt[v].rs,mid+,r,l1,r1);
} bool check(int lim)
{
int l,r,L,R;
l=,r=Rank[c]-,L=Rank[c];
while (l<=r)
{
int mid=(l+r)>>;
if (Query(mid+,Rank[c])>=lim) L=mid,r=mid-;
else l=mid+;
}
l=Rank[c]+,r=n-,R=Rank[c];
while (l<=r)
{
int mid=(l+r)>>;
if (Query(Rank[c]+,mid)>=lim) R=mid,l=mid+;
else r=mid-;
}
if (Query(Root[a],Root[b-lim+],,n,L,R)) return true;
return false;
} int main()
{
n=read(); q=read();
scanf("%s",r);
Build_SA(); Build_Height();
Build_ST();
for (int i=; i<=n; ++i)
Root[i]=Update(Root[i-],,n,Rank[i-]);
while (q--)
{
a=read()-; b=read()-; c=read()-; d=read()-;
int l=,r=min(b-a+,d-c+),ans=;
while (l<=r)
{
int mid=(l+r)>>;
if (check(mid)) ans=mid, l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
}