字符串[未AC]（后缀自动机）：HEOI 2016 str

　　超级恶心，先后用set维护right，再用主席树维护，全部超时，本地测是AC的。放心，BZOJ上还是1S限制，貌似只有常数优化到一定境界的人才能AC吧。

　　总之我是精神胜利了哦耶QAQ

#include <iostream>
#include <cstring>
#include <cstdio>
#define lb lower_bound
#define ub upper_bound
#include <set>
using namespace std;
const int N=200010;
int fa[N][20],ch[N][2],len[N],pos[N];
int lst,cnt;set<int>t[N];
int n,Q,a,b,c,d;char s[N];
void Init(){lst=cnt=1;}
void Insert(int c){
    int p=lst,np=lst=++cnt;len[np]=len[p]+1;
    while(p&&ch[p][c]==0)ch[p][c]=np,p=fa[p][0];
    if(!p)fa[np][0]=1;
    else{
        int q=ch[p][c],nq;
        if(len[q]==len[p]+1)fa[np][0]=q;
        else{
            len[nq=++cnt]=len[p]+1;
            fa[nq][0]=fa[q][0];fa[q][0]=fa[np][0]=nq;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            while(ch[p][c]==q)ch[p][c]=nq,p=fa[p][0];
        }
    }
}
int cntE,fir[N],to[N],nxt[N];
void addedge(int a,int b){
    nxt[++cntE]=fir[a];
    to[fir[a]=cntE]=b;
}
 
set<int>Merge(set<int>x,set<int>y){
    if(x.size()<y.size())swap(x,y);
    x.insert(y.begin(),y.end());
    //delete &y;
    return x;
}
 
void DFS(int x){
    for(int i=fir[x];i;i=nxt[i])
        DFS(to[i]),t[x]=Merge(t[x],t[to[i]]);
}
 
bool Judge(int p,int l,int r){
    return t[p].lb(l)!=t[p].ub(r);
}

int Find(int x,int l){
    for(int i=17;i>=0;i--)
        if(fa[x][i]&&len[fa[x][i]]>=l)
            x=fa[x][i];
    return x;        
}

int Solve(){
    int l=0,r=min(d-c,b-a)+1;
    while(l<=r){
        int mid=(l+r)>>1;
        int p=Find(pos[c],mid);
        if(Judge(p,a,b-mid+1))l=mid+1;
        else r=mid-1;
    }
    return r;
}


int main(){
    freopen("heoi2016_str5.in","r",stdin);
    freopen("heoi2016_str.out","w",stdout);
    Init();scanf("%d%d%s",&n,&Q,s+1);
    for(int i=n;i>=1;i--){Insert(s[i]-'a');t[pos[i]=lst].insert(i);}
    for(int i=2;i<=cnt;i++)addedge(fa[i][0],i);DFS(1);
    for(int k=1;k<=17;k++)
        for(int i=1;i<=cnt;i++)
            fa[i][k]=fa[fa[i][k-1]][k-1];
    while(Q --){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d
",Solve());
    }
    return 0;
}

　　然后是应该AC的：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
using namespace std;
const int N=200010;
int fa[N][20],ch[N][26],len[N],pos[N];
int lst,cnt,n,Q;char s[N];
void Init(){lst=cnt=1;}
void Insert(int c){
    int p=lst,np=lst=++cnt;len[np]=len[p]+1;
    while(p&&ch[p][c]==0)ch[p][c]=np,p=fa[p][0];
    if(!p)fa[np][0]=1;
    else{
        int q=ch[p][c],nq;
        if(len[q]==len[p]+1)fa[np][0]=q;
        else{
            len[nq=++cnt]=len[p]+1;
            fa[nq][0]=fa[q][0];fa[q][0]=fa[np][0]=nq;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            while(ch[p][c]==q)ch[p][c]=nq,p=fa[p][0];
        }
    }
}
int cntE,fir[N],to[N],nxt[N];
void addedge(int a,int b){
    nxt[++cntE]=fir[a];
    to[fir[a]=cntE]=b;
}
 
int id[N],ed[N],tot;
int rt[N],sum[N*25],son[N*25][2];
void Insert(int pre,int &rt,int l,int r,int g){
    sum[rt=++tot]=sum[pre]+1;
    son[rt][0]=son[pre][0];
    son[rt][1]=son[pre][1];
    if(l==r)return;int mid=l+r>>1;
    if(mid>=g)Insert(son[pre][0],son[rt][0],l,mid,g);
    else Insert(son[pre][1],son[rt][1],mid+1,r,g);
}
int Query(int x,int l,int r,int a,int b){
    if(l>=a&&r<=b||!sum[x])return sum[x];
    int ret=0,mid=l+r>>1;
    if(mid>=a)ret=Query(son[x][0],l,mid,a,b);
    if(mid<b)ret+=Query(son[x][1],mid+1,r,a,b);
    return ret;
}
 
bool Judge(int p,int l,int r){
    int A=Query(rt[l-1],1,cnt,id[p],ed[p]);
    int B=Query(rt[r],1,cnt,id[p],ed[p]);
    return A<B;
}

int st[N],top;
int main(){
    freopen("heoi2016_str.in","r",stdin);
    freopen("heoi2016_str.out","w",stdout);
    Init();scanf("%d%d%s",&n,&Q,s+1);
    for(int i=n;i>=1;i--)Insert(s[i]-'a'),pos[i]=lst;
    for(int i=2;i<=cnt;i++)addedge(fa[i][0],i);
    for(int k=1;k<=18;k++)for(int i=1;i<=cnt;i++)
        fa[i][k]=fa[fa[i][k-1]][k-1];
    st[top=1]=1;
    while(top){
        int x=st[top];
        if(id[x]){ed[x]=tot;top--;}
        else{
            id[x]=++tot;
            for(int i=fir[x];i;i=nxt[i])
                st[++top]=to[i];
        }
    }
    
    tot=0;
    for(int i=1;i<=n;i++)
        Insert(rt[i-1],rt[i],1,cnt,id[pos[i]]);    
    int a,b,c,d;    
    while(Q --){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int l=0,r=min(d-c,b-a)+1;
        while(l<=r){
            int mid=l+r>>1,p=pos[c];
            for(int i=18;i>=0;i--)
                if(fa[p][i]&&len[fa[p][i]]>=mid)
                    p=fa[p][i];
            if(Judge(p,a,b-mid+1))l=mid+1;
            else r=mid-1;
        }
        printf("%d
",r);
    }
    //printf("%lf
", (double)clock()/CLOCKS_PER_SEC);
    return 0;
}

 　　有毒啊，后缀数组都写挂了，TLE。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=100010;
int n,Q,r[N],Wa[N],Wb[N],Wv[N],Ws[N];
int rk[N],sa[N],lcp[N],mm[N],Min[N][20];
int len,cnt,ch[N*20][2],sum[N*20],rt[N];
char s[N];
bool cmp(int *p,int i,int j,int l){
    return p[i]==p[j]&&p[i+l]==p[j+l];
}

void DA(int n,int m){
    int i,j,p,*x=Wa,*y=Wb;
    for(i=0;i<m;i++)Ws[i]=0;
    for(i=0;i<n;i++)++Ws[x[i]=r[i]];
    for(i=1;i<m;i++)Ws[i]+=Ws[i-1];
    for(i=n-1;i>=0;i--)sa[--Ws[x[i]]]=i;
    
    for(p=1,j=1;p<n;m=p,j<<=1){
        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++)Ws[i]=0;
        for(i=0;i<n;i++)++Ws[Wv[i]=x[y[i]]];
        for(i=1;i<m;i++)Ws[i]+=Ws[i-1];
        for(i=n-1;i>=0;i--)sa[--Ws[Wv[i]]]=y[i];
        for(swap(x,y),x[sa[0]]=0,i=1,p=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}

void LCP(int n){
    int i,j,k=0;
    for(i=1;i<=n;i++)rk[sa[i]]=i;
    for(i=0;i<n;lcp[rk[i++]]=k)
        for(k-=k>0,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);
}

#define mid ((l+r)>>1)
void Insert(int pre,int &rt,int l,int r,int g,int d){
    sum[rt=++cnt]=sum[pre]+d;ch[rt][0]=ch[pre][0];
    ch[rt][1]=ch[pre][1];if(l==r)return;
    if(mid>=g)Insert(ch[pre][0],ch[rt][0],l,mid,g,d);
    else Insert(ch[pre][1],ch[rt][1],mid+1,r,g,d);
}

int Query(int pre,int rt,int l,int r,int a,int b){
    if(l>=a&&r<=b)return sum[rt]-sum[pre];int ret=0;
    if(mid>=a)ret=Query(ch[pre][0],ch[rt][0],l,mid,a,b);
    if(mid<b)ret+=Query(ch[pre][1],ch[rt][1],mid+1,r,a,b);
    return ret;
}

void Prepare(int n){
    mm[0]=-1;
    for(int i=1;i<=n;i++){
        mm[i]=mm[i-1];
        if(!(i&i-1))mm[i]+=1;
        Min[i][0]=lcp[i];
    }
    for(int k=1;k<=mm[n];k++)
        for(int i=1;i+(1<<k-1)<=n;i++)
            Min[i][k]=min(Min[i][k-1],Min[i+(1<<k-1)][k-1]);
}

int Qmin(int x,int y){
    if(x>y)swap(x,y);x+=1;int l=mm[y-x+1];
    return min(Min[x][l],Min[y-(1<<l)+1][l]);
}

int a,b,c,d,lo,hi;
bool Check(int x,int n){
    int l=1,r=rk[c-1]-1,pl,pr;
    while(l<=r){
        if(Qmin(mid,rk[c-1])>=x)r=mid-1;
        else l=mid+1;    
    }pl=l;
    l=rk[c-1]+1,r=n;
    while(l<=r){
        if(Qmin(rk[c-1],mid)>=x)l=mid+1;
        else r=mid-1;
    }pr=r;
    return Query(rt[pl-1],rt[pr],1,n,a,b-x+1);
}

int main(){
    freopen("heoi2016_str.in","r",stdin);
    freopen("heoi2016_str.out","w",stdout);
    scanf("%d%d%s",&n,&Q,s);
    for(;s[len];len++)r[len]=s[len];
    DA(len+1,128);LCP(len);Prepare(len);
    for(int i=1;i<=len;i++)
        Insert(rt[i-1],rt[i],1,len,sa[i]+1,1);
    while(Q--){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        lo=1,hi=min(b-a+1,d-c+1);
        while(lo<=hi){
            int MID=(lo+hi)>>1;
            if(Check(MID,len))lo=MID+1;
            else hi=MID-1;
        }
        printf("%d
",hi);
    }
    return 0;
}