虽然有准备但是调得就像失了智一样

首先我们先跑一次后缀数组

对于答案二分，找出C的Rank，左右延伸，看最远可以满足的L、R，这个可以通过st表实现

那么对于A~B的字串，它所要满足的，就是A<=i<=B，L<=Rank[i]<=R

那么就按照Rank建主席树，把i插入，查找就找区间L~R内有没有A~B的值

PS：st表那里用倍增应该比较快，但是我没有调出来，那么我就大力二分左右边界，用RMQ求区间最值

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n;char ss[110000];int sa1[110000],Rank[110000];int sa2[110000],tt[110000],Rsort[110000];void get_sa(int m){ for(int i=1;i<=n;i++)Rank[i]=ss[i]-'a'+1; memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=n;i++)Rsort[Rank[i]]++; for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1]; for(int i=n;i>=1;i--)sa1[Rsort[Rank[i]]--]=i; int ln=1,p=0; while(p
           
            0)sa2[++k]=sa1[i]-ln; memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=n;i++)Rsort[Rank[sa2[i]]]++; for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1]; for(int i=n;i>=1;i--)sa1[Rsort[Rank[sa2[i]]]--]=sa2[i]; for(int i=1;i<=n;i++)tt[i]=Rank[i]; p=1;Rank[sa1[1]]=p; for(int i=2;i<=n;i++) { if(tt[sa1[i]]!=tt[sa1[i-1]]||tt[sa1[i]+ln]!=tt[sa1[i-1]+ln])p++; Rank[sa1[i]]=p; } ln*=2;m=p; }}int height[110000];void get_he(){ int j,h=0; for(int i=1;i<=n;i++) { j=sa1[Rank[i]-1]; if(h!=0)h--; while(ss[i+h]==ss[j+h])h++; height[Rank[i]]=h; }}//----------------SA----------------------------int Bin[30],Log[110000],f[25][110000];void get_st(){ Bin[0]=1;for(int i=1;i<=25;i++)Bin[i]=Bin[i-1]*2; Log[1]=0;for(int i=2;i<=n ;i++)Log[i]=Log[i/2]+1; for(int i=1;i<=n;i++)f[0][i]=height[i]; for(int j=1;Bin[j]<=n;j++) for(int i=1;i+Bin[j]-1<=n;i++) f[j][i]=min(f[j-1][i],f[j-1][i+Bin[j-1]]);}int RMQ(int x,int y){ if(x>y)swap(x,y); int k=Log[y-x+1]; return min(f[k][x],f[k][y-Bin[k]+1]);}int L,R;void getLR(int u,int d){ int l,r;L=u,R=u; l=2,r=u; while(l<=r) { int mid=(l+r)/2; if(RMQ(mid,u)>=d) { L=mid-1; r=mid-1; } else l=mid+1; } l=u+1,r=n; while(l<=r) { int mid=(l+r)/2; if(RMQ(mid,u+1)>=d) { R=mid; l=mid+1; } else r=mid-1; }}//---------------get_st----------------------struct chairman_tree{ int lc,rc,c;}tr[5100000];int trlen,rt[110000];int maketree(int now,int l,int r,int p){ if(now==0) { now=++trlen; tr[now].lc=tr[now].rc=0; tr[now].c=0; } tr[now].c++; if(l==r)return now; else { int mid=(l+r)/2; if(p<=mid)tr[now].lc=maketree(tr[now].lc,l,mid,p); else tr[now].rc=maketree(tr[now].rc,mid+1,r,p); return now; }}int merge(int x,int y){ if(x==0||y==0)return x+y; tr[x].c+=tr[y].c; tr[x].lc=merge(tr[x].lc,tr[y].lc); tr[x].rc=merge(tr[x].rc,tr[y].rc); return x;}//init~~~bool check(int x,int y,int l,int r,int ll,int rr){ if(tr[y].c-tr[x].c==0)return false; if(l==ll&&r==rr)return true; int mid=(l+r)/2; if(rr<=mid) return check(tr[x].lc,tr[y].lc,l,mid,ll,rr); else if(mid+1<=ll)return check(tr[x].rc,tr[y].rc,mid+1,r,ll,rr); else return (check(tr[x].lc,tr[y].lc,l,mid,ll,mid)|check(tr[x].rc,tr[y].rc,mid+1,r,mid+1,rr));}//--------------chairman_tree------------------------int main(){ freopen("str.in","r",stdin); freopen("str.out","w",stdout); int Q; scanf("%d%d",&n,&Q); scanf("%s",ss+1); get_sa(100);get_he(); get_st(); trlen=0;memset(rt,0,sizeof(rt)); for(int i=1;i<=n;i++)//枚举排名 { rt[i]=maketree(rt[i],1,n,sa1[i]); rt[i]=merge(rt[i],rt[i-1]); } int A,B,C,D; while(Q--) { scanf("%d%d%d%d",&A,&B,&C,&D); int l=1,r=min(B-A+1,D-C+1),ans=0; while(l<=r) { int mid=(l+r)/2; getLR(Rank[C],mid); if(check(rt[L-1],rt[R],1,n,A,B-mid+1)==true) { l=mid+1; ans=mid; } else r=mid-1; } printf("%d\n",ans); } return 0;}