【BZOJ4556】[Tjoi2016&Heoi2016]字符串
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
题解：先求后缀数组，我们找到[c..d]的rank值，如果不考虑b和d的影响（即我们求的是两个后缀LCP），那么显然最优的a的rank值一定是c的前驱或者后继。那么如何求一段区间中，rank值的前驱或后继呢？用可持久化线段树维护，再用RMQ求LCP即可。
但是题中给出的后缀是有长度限制的（即子串），怎么办？二分答案！我们只求[a,b-mid+1]这段中的前驱后继，用这个来更新答案，就不用考虑长度限制了。
#include <cstdio>
#include <cstring>
#include <iostream> const int maxn=100010;
using namespace std;
int n,Q,m,tot,ans;
int r[maxn],ra[maxn],rb[maxn],sa[maxn],st[maxn],rank[maxn],h[maxn],f[18][maxn],Log[maxn],rt[maxn];
struct sag
{
int ls,rs,siz;
}s[maxn*30];
char str[maxn];
inline void build()
{
int i,j,*x=ra,*y=rb,k,p;
for(i=0;i<n;i++) st[x[i]=r[i]]++;
for(i=1;i<m;i++) st[i]+=st[i-1];
for(i=n-1;i>=0;i--) sa[--st[x[i]]]=i;
for(j=p=1;p<n;j<<=1,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<m;i++) st[i]=0;
for(i=0;i<n;i++) st[x[y[i]]]++;
for(i=1;i<m;i++) st[i]+=st[i-1];
for(i=n-1;i>=0;i--) sa[--st[x[y[i]]]]=y[i];
for(i=p=1,swap(x,y),x[sa[0]]=0;i<n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
for(i=1;i<n;i++) rank[sa[i]]=i;
for(i=k=0;i<n-1;h[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
for(i=1;i<n;i++) f[0][i]=h[i];
for(i=2;i<=n;i++) Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<n;j++) for(i=1;i+(1<<j)-1<n;i++) f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
}
void insert(int x,int &y,int l,int r,int a)
{
y=++tot,s[y].siz=s[x].siz+1;
if(l==r) return ;
int mid=(l+r)>>1;
if(a<=mid) s[y].rs=s[x].rs,insert(s[x].ls,s[y].ls,l,mid,a);
else s[y].ls=s[x].ls,insert(s[x].rs,s[y].rs,mid+1,r,a);
}
int getrank(int l,int r,int x,int y,int a)
{
if(l==r) return s[y].siz-s[x].siz;
int mid=(l+r)>>1;
if(a<=mid) return getrank(l,mid,s[x].ls,s[y].ls,a);
else return s[s[y].ls].siz-s[s[x].ls].siz+getrank(mid+1,r,s[x].rs,s[y].rs,a);
}
int find(int l,int r,int x,int y,int a)
{
if(a>s[y].siz-s[x].siz) return -1;
if(l==r) return l;
int mid=(l+r)>>1;
if(a<=s[s[y].ls].siz-s[s[x].ls].siz) return find(l,mid,s[x].ls,s[y].ls,a);
return find(mid+1,r,s[x].rs,s[y].rs,a-s[s[y].ls].siz+s[s[x].ls].siz);
}
inline int query(int a,int b)
{
if(a==-1) return 0;
if(a==b) return n-sa[a];
if(a>b) swap(a,b);
a++;
int k=Log[b-a+1];
return min(f[k][a],f[k][b-(1<<k)+1]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
inline bool check(int a,int b,int c,int len)
{
int x=getrank(0,n,rt[a],rt[b+1],c);
if(query(find(0,n,rt[a],rt[b+1],x),c)>=len) return 1;
if(query(find(0,n,rt[a],rt[b+1],x+1),c)>=len) return 1;
return 0;
}
int main()
{
n=rd(),Q=rd();
int i,a,b,c,d;
scanf("%s",str);
for(i=0;i<n;i++) r[i]=str[i]-'a'+1,m=max(m,r[i]+1);
n++,build(),n--;
for(i=0;i<n;i++) insert(rt[i],rt[i+1],0,n,rank[i]);
for(i=1;i<=Q;i++)
{
a=rd()-1,b=rd()-1,c=rd()-1,d=rd()-1;
int l=0,r=min(d-c,b-a)+2,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(a,b-mid+1,rank[c],mid)) l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
}
return 0;
}//5 5 aaaaa 1 1 1 5 1 5 1 1 2 3 2 3 2 4 2 3 2 3 2 4