题解 P4770 【[NOI2018]你的名字】

mrsrz · 2018-12-21 20:58:47 · 题解

来一发后缀数组的大常数写法。

我们考虑对于一个询问，先求出T中本质不同的子串个数，然后减去是S(l,r)子串的。

本质不同的子串个数，直接用height数组的性质就可以求。具体见2408那题。

我们考虑，对于T的每一个后缀，求出其最长的前缀长度L，使得该后缀长度为L的前缀是S(l,r)的子串。

把S和所有T连起来建后缀数组。为了方便计算每个询问，我们用链表的方法，记录每个位置在同一个串中的前驱后继。

然后我们按顺序考虑T的每一个后缀。

如果a位置的后缀的满足条件的最长前缀为L,，则a+1位置的至少为L-1。原理和求height数组相同，两边都同时去掉第一个字符，至少还留下L-1。

所以考虑每个位置的话，用双指针扫描一下即可。

然后，假如我们现在考虑位置a的长度为L的前缀是否可行，就是相当于在S的[l,r-L+1]内找一个位置b，满足LCP(a,b)\geqslant L。

满足LCP(a,b)\geqslant L条件的在后缀数组上的区间[ll,rr]，可以二分，配合height数组的ST表在O(\log n)的时间内求出。

然后问题转化为询问在后缀数组上的区间[ll,rr]内，是否存在一个在S的[l,r-l+1]中的字符。这个问题可以用建主席树然后询问，单次查询时间复杂度O(\log n)。

对于一个位置，它与后缀数组上一个位置可能会算重，所以要减掉它们的LCP。由于两个位置可能不连续，这部分也要用ST表来查。

所以总时间复杂度O(n\log n)。n=|S|+\sum|T|。

常数巨大，几乎卡着时限过的QAQ。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500505
#define M 1800505
#define reg register
#define lg2(x)(31-__builtin_clz(x))
typedef long long LL;
int n,sa[M],height[M],x[M],s[M],mgk,bel[M],m,QL[N],QR[N],y[M],st[22][M],nxt[M],head[N],node=0,rt[M],pp[M],len[N];
int ls[M*20],rs[M*20],sz[M*20];
char ss[N];
bool isk;
int _L,_R;
void add(int&o,int pr,int l,int r,int pos){
    sz[o=++node]=sz[pr]+1;
    if(l<r){
        const int mid=l+r>>1;
        if(pos<=mid)add(ls[o],ls[pr],l,mid,pos),rs[o]=rs[pr];else add(rs[o],rs[pr],mid+1,r,pos),ls[o]=ls[pr];
    }
}
void sort(){
    int m=mgk,c[M];
    for(int i=1;i<=m;++i)c[i]=0;
    for(int i=1;i<=n;++i)++c[x[i]=s[i]];
    for(int i=1;i<=m;++i)c[i]+=c[i-1];
    for(int i=n;i;--i)sa[c[x[i]]--]=i;
    for(int k=1,p;k<=n;k<<=1){
        p=0;
        for(int i=n-k+1;i<=n;++i)y[++p]=i;
        for(reg int i=1;i<=n;++i)if(sa[i]>k)y[++p]=sa[i]-k;
        for(reg int i=1;i<=m;++i)c[i]=0;
        for(reg int i=1;i<=n;++i)++c[x[i]];
        for(reg int i=1;i<=m;++i)c[i]+=c[i-1];
        for(reg int i=n;i;--i)sa[c[x[y[i]]]--]=y[i];
        std::swap(x,y);
        x[sa[1]]=p=1;
        for(int i=2;i<=n;++i)
        x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
        if(p==n)break;
        m=p;
    }
    for(int i=1,k=0;i<=n;++i)
    if(x[i]>1){
        k-=!!k;
        const int j=sa[x[i]-1];
        while(s[i+k]==s[j+k])++k;
        height[x[i]]=k;
    }
}
inline int find(int l,int r){
    if(l>r)return n;
    const int lg=lg2(r-l+1);
    return std::min(st[lg][l],st[lg][r-(1<<lg)+1]);
}
void init(){
    for(reg int i=1;i<=n;++i)st[0][i]=height[i];
    for(int i=0;i<21;++i)
    for(reg int j=1;j<=n;++j)
    if(j+(1<<i)<=n)st[i+1][j]=std::min(st[i][j],st[i][j+(1<<i)]);else break;
    int pre[N];
    memset(pre,0,sizeof pre);
    for(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;
    }
}
void query(const int&ri,const int&le,int l,int r){
    if(sz[ri]==sz[le]||isk)return;
    if(_L<=l&&r<=_R)return(void)(isk=1);
    const int mid=l+r>>1;
    if(_L<=mid)query(ls[ri],ls[le],l,mid);
    if(mid<_R&&!isk)query(rs[ri],rs[le],mid+1,r);
}
bool check(int pos,int len,int l,int r){
    int L,ll,rr;
    ll=1,rr=pos-1;
    while(ll<=rr){
        const int mid=ll+rr>>1;
        if(find(mid+1,pos)>=len)rr=mid-1;else ll=mid+1;
    }
    L=rr;
    ll=pos+1,rr=n;
    while(ll<=rr){
        const int mid=ll+rr>>1;
        if(find(pos+1,mid)>=len)ll=mid+1;else rr=mid-1;
    }
    isk=0;
    _L=l,_R=r;
    query(rt[ll-1],rt[L],1,n);
    return isk;
}
int main(){
    memset(bel,-1,sizeof bel);
    mgk='z'+1;
    scanf("%s",ss);
    for(int i=0;ss[i];++i)
    s[++n]=ss[i],bel[n]=0;
    s[++n]=mgk++;
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        scanf("%s%d%d",ss,QL+i,QR+i);
        for(int j=0;ss[j];++j)
        s[++n]=ss[j],bel[n]=i;
        len[i]=n;
        s[++n]=mgk++;
    }
    sort();
    init();
    for(reg 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(int i=1;i<=m;++i){
        LL ans=len[i]-sa[head[i]]+1;
        int mnid=sa[head[i]];
        for(int j=nxt[head[i]];j;j=nxt[j]){
            ans+=len[i]-sa[j]+1;
            ans-=find(pp[j]+1,j);
            mnid=std::min(mnid,sa[j]);
        }
        for(int j=mnid,L=mnid;s[j]<='z';++j){
            if(L<j)L=j;
            while(s[L]<='z'&&check(x[j],L-j+1,QL[i],QR[i]-L+j))++L;
            if(x[j]!=head[i])ans-=std::max(L-j-find(pp[x[j]]+1,x[j]),0);else
            ans-=L-j;
        }
        printf("%lld\n",ans);
    }
    return 0;
}