代码

#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500005
#define M 1600005
#define LL long long
using namespace std;
inline void write(register LL x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
inline int Min(register int a,register int b)
{
    return a<b?a:b;
}
inline int Max(register int a,register int b)
{
    return a>b?a:b;
}
int n,size,s[M];
int tp[M],rak[M],sa[M],tex[M],height[M];
int lg2[M],st[M][25];
int nxt[M],head[M],pp[M];
int bel[M],lim,q,ql[N],qr[N],len[N];
int node,rt[M],ls[M*20],rs[M*20],sz[M*20];
char s0[N];
inline void Qsort()
{
    for(register int i=0;i<=size;++i)
        tex[i]=0;
    for(register int i=1;i<=n;++i)
        ++tex[rak[i]];
    for(register int i=1;i<=size;++i)
        tex[i]+=tex[i-1];
    for(register int i=n;i>=1;--i)
        sa[tex[rak[tp[i]]]--]=tp[i];
}
inline void sa_build()
{
    size=lim+5;
    for(register int i=1;i<=n;++i)
        rak[i]=s[i],tp[i]=i;
    Qsort();
    for(register int w=1,p=0;p<n;size=p,w<<=1)
    {
        p=0;
        for(register int i=1;i<=w;++i)
            tp[++p]=n-w+i;
        for(register int i=1;i<=n;++i)
            if(sa[i]>w)
                tp[++p]=sa[i]-w;
        Qsort();
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for(register int i=2;i<=n;++i)
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
    }
}
inline void getheight()
{
    int k=0;
    for(register int i=1;i<=n;++i)
    {
        if(k)
            --k;
        int j=sa[rak[i]-1];
        while(s[i+k]==s[j+k])
            ++k;
        height[rak[i]]=k;
    }
}
inline void st_build()
{
    lg2[0]=-1;
    for(register int i=1;i<n+2;++i)
        lg2[i]=lg2[i>>1]+1;
    lg2[0]=0;
    for(register int i=1;i<=n;++i)
        st[i][0]=height[i];
    for(register int j=1;(1<<j)<=n;++j)
        for(register int i=1;i+(1<<j)-1<=n;++i)
            st[i][j]=Min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    int pre[N];
    memset(pre,0,sizeof(pre));
    for(register int i=1;i<=n;++i)
        if(s[sa[i]]<='z')
        {
            if(pre[bel[sa[i]]])
                nxt[pre[bel[sa[i]]]]=i,pp[i]=pre[bel[sa[i]]];
            else
                head[bel[sa[i]]]=i;
            pre[bel[sa[i]]]=i;
        }
}
inline int getlcp(register int l,register int r)
{
    if(l>r)
        return n;
    int k=lg2[r-l+1];
    return Min(st[l][k],st[r-(1<<k)+1][k]);
}
inline void add(register int &x,register int pr,register int l,register int r,register int pos)
{
    sz[x=++node]=sz[pr]+1;
    if(l<r)
    {
        int mid=l+r>>1;
        if(pos<=mid)
            add(ls[x],ls[pr],l,mid,pos),rs[x]=rs[pr];
        else
            add(rs[x],rs[pr],mid+1,r,pos),ls[x]=ls[pr];
    }
}
bool flag=0;
int QL,QR;
inline void query(register int ri,register int le,register int l,register int r)
{
    if(sz[ri]==sz[le]||flag)
        return;
    if(QL<=l&&r<=QR)
    {
        flag=1;
        return;
    }
    int mid=l+r>>1;
    if(QL<=mid)
        query(ls[ri],ls[le],l,mid);
    if(QR>mid&&!flag)
        query(rs[ri],rs[le],mid+1,r); 
}
inline bool check(register int pos,register int len,register int l,register int r)
{
    int lb,rb,ll,rr;
    ll=1,rr=pos-1;
    while(ll<=rr)
    {
        int mid=ll+rr>>1;
        if(getlcp(mid+1,pos)>=len)
            rr=mid-1;
        else
            ll=mid+1;
    }
    lb=rr;
    ll=pos+1,rr=n;
    while(ll<=rr)
    {
        int mid=ll+rr>>1;
        if(getlcp(pos+1,mid)>=len)
            ll=mid+1;
        else
            rr=mid-1;
    }
    rb=ll-1;
    flag=0,QL=l,QR=r;
    query(rt[rb],rt[lb],1,n);
    return flag;
}
int main()
{
    memset(bel,-1,sizeof(bel));
    lim='z'+1;
    scanf("%s",s0);
    for(register int i=0;s0[i];++i)
        s[++n]=s0[i],bel[n]=0;
    s[++n]=lim++;
    scanf("%d",&q);
    for(register int i=1;i<=q;++i)
    {
        scanf("%s%d%d",s0,&ql[i],&qr[i]);
        for(register int j=0;s0[j];++j)
            s[++n]=s0[j],bel[n]=i;
        len[i]=n;
        s[++n]=lim++;
    }
    sa_build();
    getheight();
    st_build();
    for(register int i=1;i<=n;++i)
        if(!bel[sa[i]])
            add(rt[i],rt[i-1],1,n,sa[i]);
        else
            rt[i]=rt[i-1];
    for(register int i=1;i<=q;++i)
    {
        LL ans=len[i]-sa[head[i]]+1;
        int minn=sa[head[i]];
        for(register int j=nxt[head[i]];j;j=nxt[j])
        {
            ans+=len[i]-sa[j]+1-getlcp(pp[j]+1,j);
            minn=Min(minn,sa[j]);
        } 
        for(register int j=minn,L=minn;s[j]<='z';++j)
        {
            if(L<j)
                L=j;
            while(s[L]<='z'&&check(rak[j],L-j+1,ql[i],qr[i]-L+j))
                ++L;
            if(rak[j]!=head[i])
                ans-=Max(L-j-getlcp(pp[rak[j]]+1,rak[j]),0);
            else
                ans-=L-j;
        }
        write(ans),puts("");
    }
    return 0;
}

评测结果