![[BZOJ4556][Tjoi2016&Heoi2016]字符串 后缀数组+主席树](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[BZOJ4556][Tjoi2016&Heoi2016]字符串 后缀数组+主席树")
4556: [Tjoi2016&Heoi2016]字符串
Time Limit: 20 Sec Memory Limit: 128 MB
Description
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了
一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CE
O，嫁给高富帅，走上人生巅峰。每个问题均有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
题解：
真是太刺激了。。第一次发现后缀数组可以和高级数据结构联系起来233
（不过据说正解并不是裸跑后缀数组……）
首先，我们容易想到二分答案求解，但是二分之后怎么处理呢？
我们考虑，对于这个二分的长度x，rank[c]附近一定可以形成一段区间，使得他们的lcp大于等于x(rank[c]自己的lcp是串长)
这一段区间的查询我们可以通过ST表进行查询
接下来,如果[a,b]范围内有一个串存在于那个区间里就好了,
那么我们考虑,如何查询某个区间内的一些给定值是否出现某个值呢?
这种查询的特点不难让我们想到主席树"切割区间"的功能:
即查询a到b-x+1(如果x等于0,那么这个端点是b)区间内是否有一个rank值处在刚才查找到的区间,
我们可以通过主席树这种权值线段树记录这个存在性问题
这样不断判断合法性即可,复杂度是nlogn预处理+mlog2n查询的,因此可以AC.
代码实现:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int cnt[N],xx[N],yy[N],n;
char s[N];
int rank[N],sa[N],height[N],bin[],f[N][];
inline void get_sa(int m)
{
int *x=xx,*y=yy;
register int i,j,p,k;
for(i=;i<m;++i)cnt[i]=;
for(i=;i<n;++i)++cnt[x[i]=s[i]];
for(i=;i<m;++i)cnt[i]+=cnt[i-];
for(i=n-;~i;--i)sa[--cnt[x[i]]]=i;
for(k=,p=;k<=n&&p<n;k<<=,m=p)
{
for(p=,i=n-k;i<n;++i)y[p++]=i;
for(i=;i<n;++i)if(sa[i]>=k)y[p++]=sa[i]-k;
for(i=;i<m;++i)cnt[i]=;
for(i=;i<n;++i)++cnt[x[y[i]]];
for(i=;i<m;++i)cnt[i]+=cnt[i-];
for(i=n-;~i;--i)sa[--cnt[x[y[i]]]]=y[i];
swap(x,y),x[sa[]]=,p=;
for(i=;i<n;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k])?p-:p++;
}
}
inline void get_height()
{
register int i,j,k;
for(i=;i<n;++i)rank[sa[i]]=i;
for(k=i=;i<n;height[rank[i++]]=k)
for(k=k?k-:k,j=sa[rank[i]-];s[i+k]==s[j+k];++k);
}
inline void ST()
{
register int i,j;
for(bin[]=i=;i<=;++i)
bin[i]=bin[i-]<<;
for(j=;j<n;++j)f[j][]=height[j];
for(i=;bin[i-]<=n;++i)
for(j=;j+bin[i]<=n;++j)
f[j][i]=min(f[j][i-],f[j+bin[i-]][i-]);
}
struct node
{
node *ch[];int cnt;
node(){ch[]=ch[]=NULL;cnt=;}
inline void update(){cnt=ch[]->cnt+ch[]->cnt;}
}*null=new node(),*root[N];
inline node* newnode()
{node *o=new node();o->ch[]=o->ch[]=null;return o;}
inline bool query(node *a,node *b,int L,int R,int l,int r)
{
if(L<=l&&r<=R)return b->cnt-a->cnt;
int mi=l+r>>;bool ret=;
if(L<=mi)ret|=query(a->ch[],b->ch[],L,R,l,mi);
if(mi<R)ret|=query(a->ch[],b->ch[],L,R,mi+,r);
return ret;
}
inline void get_range(int val,int &l,int &r)
{
register int j;
for(j=;~j&&r<n;--j)
if(r+bin[j]-<n&&f[r+][j]>=val)r+=bin[j];
for(j=;~j&&l;--j)
if(l-bin[j]+>=&&f[l-bin[j]+][j]>=val)l-=bin[j];
}
inline bool judge(int a,int b,int c,int minimum)
{
int l=rank[c],r=rank[c],right=minimum?b-minimum+:b;
get_range(minimum,l,r);
if(query(a?root[a-]:null,root[right],l,r,,n-))return ;
return ;
}
inline void insert(node *&o,node *old,int l,int r,int pos)
{
o->cnt=old->cnt+;int mi=(l+r)>>;if(l==r)return;
if(pos<=mi)
o->ch[]=old->ch[],o->ch[]=newnode(),
insert(o->ch[],old->ch[],l,mi,pos);
else
o->ch[]=old->ch[],o->ch[]=newnode(),
insert(o->ch[],old->ch[],mi+,r,pos);
o->update();
}
inline void Tree_intn()
{
register int i;
null->ch[]=null->ch[]=null;
for(i=;i<n;++i)root[i]=newnode();
insert(root[],null,,n-,rank[]);
for(i=;i<n;++i)
insert(root[i],root[i-],,n-,rank[i]);
}
int main()
{
register int i,j,k,a,b,c,d,m,l,mi,r,ans;
scanf("%d%d%s",&n,&m,s),s[n++]=,
get_sa(),get_height(),ST(),Tree_intn();
while(m--)
{
scanf("%d%d%d%d",&a,&b,&c,&d),--a,--b,--c,--d;
l=,mi,r=min(b-a+,d-c+),ans=;
while(l<=r)
if(judge(a,b,c,(mi=l+r>>)))l=mi+,ans=mi;
else r=mi-;
printf("%d\n",ans);
}
}