XVIII.[HEOI2016/TJOI2016]字符串
作为一个理智正常的OIer，二维数点的题说什么都应该离线线段树通过而不是大力搞主席树呀（（（
我们发现这题询问中\(s[c,\dots,d]\)中这个“\(d\)”是不重要的，只需要把最终结果同\((d-c+1)\)取\(\min\)即可，因此忽略不管。
然后这个问题就被转换成了：对于区间\([a,b]\)内所有后缀\(suf[i]\)，求\(\min\Big(\operatorname{LCP}(suf[i],suf[c]),b-i+1\Big)\)的最大值。
我们考虑二分这个最大值，设为\(mid\)。现在要来判断\(mid\)这个值是否合法。则只有区间\([a,a+mid-1]\)中的\(\operatorname{LCP}\)才可能达到这么长，故只要找到其中的\(\max\text{LCP}\)，如果其长度大于等于\(mid\)，则\(mid\)合法。
到现在我们已经可以构思出一个\(O(n\log^2n)\)的二分套线段树的做法了。具体思路是，因为\(\max\text{LCP}\)一定在两个后缀的\(rk\)最接近时取到，所以我们将它拆成两半，一半是\(rk_i\leq rk_c\)的，一半是\(rk_i\geq rk_c\)的。
则我们需要先将询问按照\(rk_c\)排序，按顺序将位置插入线段树，在前一半中查询区间中\(rk_i\)的最大值，后一半中查询\(rk_i\)的最小值（这里的线段树是以原串位置为下标的）。在查询到这个值最大值/最小值后，就可以通过ST表求出\(\text{LCP}\)了。当然，这一切都是建立在二分的基础上，即，我们每次询问的区间都是二分出来的区间\([a,a+mid-1]\)。
但是这样子得写两棵线段树，再加上ST表，太难受了。我们不如这样，直接在线段树上维护\(\text{LCP}\)长度。办法很简单，当新加入一个位置后，直接将线段树中所有\(\text{LCP}\)长度与它取\(\min\)即可。
我们可以写出这样的pushdown函数：
#define change(x,y) seg[x].lcp=min(seg[x].lcp,y),seg[x].tag=min(seg[x].tag,y)
void pushdown(int x){
change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
}
然后在主函数只需要这样来一句change(1,ht[j])即可。
在取\(\min\)后，把对应位置的\(\text{LCP}\)长度改成\(n-i\)，因为自己跟自己的\(\text{LCP}\)长度就是串长。
这里是将一个位置插入线段树的代码：
void turnon(int x,int l,int r,int P){
if(l>P||r<P)return;
seg[x].lcp=max(seg[x].lcp,n-P);
if(l!=r)pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P);
}
到这里，我们已经省掉了ST表，并且也只用写一颗线段树了。我们要不再努力努力，干脆连二分也给省了，直接在线段树上二分？
我们设一个query函数来回答询问。我们考虑当前走到节点\(x\)，它代表的区间是\([l,r]\)，询问区间是\([L,R]\)。
-
假如\([l,r]\cup[L,R]=\emptyset\)，直接
return -1即可。 -
假如\([l,r]\subseteq[L,R]\)：
2.1. 如果\(lcp_x\geq R-r+1\)，则显然全局最优答案肯定处于区间\([l,r]\)之中，我们单独开一个getans函数来处理这种情况，马上讲。我们直接返回getans的结果，并标记找到了答案。
2.2 否则，\(lcp_x\)就是区间\([l,r]\)中的最优答案（因为没有越界），直接return lcp[x]即可。
- 否则，先递归左儿子，如果左儿子找到答案，直接
return 左儿子的答案即可；否则，return max(左儿子的答案，右儿子的答案）
至于getans函数，就是一个常规的线段树上二分，找到最小的那个满足lcp[x]>=R-r+1的位置并返回即可。
这部分代码：
int getans(int x,int l,int r,int L,int R){//this function is to find the real answer in a section
if(l==r)return min(seg[x].lcp,R-r+1);//we've reached a leaf, go back immediately.
pushdown(x);
if(seg[lson].lcp>=R-mid+1)return getans(lson,l,mid,L,R);//the answer in left son is surely the best
else return max(seg[lson].lcp,getans(rson,mid+1,r,L,R));//the left answer hasn't gone over the border, so it's the real answer
}
int query(int x,int l,int r,int L,int R,bool &findans){//this function is to find the answer to the queries
if(l>R||r<L)return -1;
if(L<=l&&r<=R){
if(seg[x].lcp>=R-r+1){findans=true;return getans(x,l,r,L,R);}//the answer here is the best answer
return seg[x].lcp;//the answer has't gone over the border, so it's the real answer
}
pushdown(x);
int tmp=query(lson,l,mid,L,R,findans);
if(findans)return tmp;
return max(tmp,query(rson,mid+1,r,L,R,findans));
}
正着来一遍，反着再来一遍，两边答案取\(\max\)即可。
总复杂度\(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,q,res[N],len[N];
namespace Suffix_Array{
int x[N],y[N],sa[N],ht[N],rk[N],buc[N];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
struct Query{
int L,R,pos,id;
Query(int a=0,int b=0,int c=0,int d=0){L=a,R=b,pos=c,id=d;}
friend bool operator <(const Query&x,const Query&y){
return x.pos<y.pos;
}
}p[N];
namespace SegMentTree{
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{//lcp stands for the maximum lcp in the section
int lcp,tag;
}seg[N<<2];
#define change(x,y) seg[x].lcp=min(seg[x].lcp,y),seg[x].tag=min(seg[x].tag,y)
void pushdown(int x){
change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
}
void build(int x,int l,int r){
seg[x].tag=0x3f3f3f3f,seg[x].lcp=-1;
if(l!=r)build(lson,l,mid),build(rson,mid+1,r);
}
void turnon(int x,int l,int r,int P){
if(l>P||r<P)return;
seg[x].lcp=max(seg[x].lcp,n-P);
if(l!=r)pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P);
}
int getans(int x,int l,int r,int L,int R){//this function is to find the real answer in a section
if(l==r)return min(seg[x].lcp,R-r+1);//we've reached a leaf, go back immediately.
pushdown(x);
if(seg[lson].lcp>=R-mid+1)return getans(lson,l,mid,L,R);//the answer in left son is surely the best
else return max(seg[lson].lcp,getans(rson,mid+1,r,L,R));//the left answer hasn't gone over the border, so it's the real answer
}
int query(int x,int l,int r,int L,int R,bool &findans){//this function is to find the answer to the queries
if(l>R||r<L)return -1;
if(L<=l&&r<=R){
if(seg[x].lcp>=R-r+1){findans=true;return getans(x,l,r,L,R);}//the answer here is the best answer
return seg[x].lcp;//the answer has't gone over the border, so it's the real answer
}
pushdown(x);
int tmp=query(lson,l,mid,L,R,findans);
if(findans)return tmp;
return max(tmp,query(rson,mid+1,r,L,R,findans));
}
#undef lson
#undef rson
#undef mid
}
using namespace SegMentTree;
int main(){
scanf("%d%d%s",&n,&q,s),m='z',SA();
for(int i=1,a,b,c,d;i<=q;i++)scanf("%d%d%d%d",&a,&b,&c,&d),p[i]=Query(a-1,b-1,rk[c-1],i),len[i]=d-c+1;
sort(p+1,p+q+1);
build(1,0,n-1);
for(int i=1,j=0;i<=q;i++){
for(;j<=p[i].pos;j++)change(1,ht[j]),turnon(1,0,n-1,sa[j]);
bool tmp=false;
res[p[i].id]=max(res[p[i].id],query(1,0,n-1,p[i].L,p[i].R,tmp));
}
build(1,0,n-1);
for(int i=q,j=n-1;i;i--){
for(;j>=p[i].pos;j--)change(1,ht[j+1]),turnon(1,0,n-1,sa[j]);
bool tmp=false;
res[p[i].id]=max(res[p[i].id],query(1,0,n-1,p[i].L,p[i].R,tmp));
}
for(int i=1;i<=q;i++)printf("%d\n",min(res[i],len[i]));
return 0;
}