[NOI2018]你的名字（后缀自动机+线段树合并）

看到题目名字去补番是种怎么样的体验

我只会 (68) 分，打了个暴力。正解看了一会儿，发现跟 ([HEOI2016/TJOI2016]) 字符串很像，用线段树合并维护 (endpos) 集合，然后一边匹配一边记录答案。

[ans=sum_{i=1}^{cnt}max(0,len_i-max(len_{fa_i},lim_{pos_i})) ]

(Code Below:)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000000+10;
int n,m,q,a[maxn],b[maxn],rt[maxn],L[maxn*40],R[maxn*40],sum[maxn*40],tot;
char s[maxn];

struct SAM{
    int last,cnt,ch[maxn][26],fa[maxn],l[maxn],pos[maxn],lim[maxn];
    void init(){
        for(int i=1;i<=cnt;i++){
            for(int j=0;j<26;j++) ch[i][j]=0;
        }
        last=cnt=1;
    }
    void insert(int c,int id){
        int p=last,q=++cnt;last=q;l[q]=l[p]+1;pos[q]=id;
        for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=q;
        if(!p) fa[q]=1;
        else {
            int r=ch[p][c];
            if(l[p]+1==l[r]) fa[q]=r;
            else {
                int s=++cnt;l[s]=l[p]+1;pos[s]=pos[r];
                memcpy(ch[s],ch[r],sizeof(ch[r]));
                fa[s]=fa[r];fa[r]=fa[q]=s;
                for(;p&&ch[p][c]==r;p=fa[p]) ch[p][c]=s;
            }
        }
    }
    ll calc(){
        ll ans=0;
        for(int i=2;i<=cnt;i++) ans+=max(0,l[i]-max(l[fa[i]],lim[pos[i]]));
        return ans;
    }
}S,T;

void update(int &now,int l,int r,int x){
    if(!now) now=++tot;
    sum[now]++;
    if(l == r) return ;
    int mid=(l+r)>>1;
    if(x <= mid) update(L[now],l,mid,x);
    else update(R[now],mid+1,r,x);
}

int merge(int x,int y){
    if(x==0||y==0) return x+y;
    int z=++tot;
    sum[z]=sum[x]+sum[y];
    L[z]=merge(L[x],L[y]);
    R[z]=merge(R[x],R[y]);
    return z;
}

int query(int now,int Le,int Ri,int l,int r){
    if(!now||Le>Ri) return 0;
    if(Le <= l && r <= Ri) return sum[now];
    int mid=(l+r)>>1,ans=0;
    if(Le <= mid) ans+=query(L[now],Le,Ri,l,mid);
    if(Ri > mid) ans+=query(R[now],Le,Ri,mid+1,r);
    return ans;
}

int main()
{
    scanf("%s",s+1);n=strlen(s+1);S.init();
    for(int i=1;i<=n;i++){
        S.insert(s[i]-'a',i);
        update(rt[S.last],1,n,i);
    }
    for(int i=1;i<=S.cnt;i++) b[S.l[i]]++;
    for(int i=1;i<=S.cnt;i++) b[i]+=b[i-1];
    for(int i=S.cnt;i>=1;i--) a[b[S.l[i]]--]=i;
    for(int i=S.cnt;i>=2;i--) rt[S.fa[a[i]]]=merge(rt[S.fa[a[i]]],rt[a[i]]);
    scanf("%d",&q);
    int l,r,p,c,len;
    while(q--){
        scanf("%s%d%d",s+1,&l,&r);m=strlen(s+1);
        T.init();len=0;p=1;
        for(int i=1;i<=m;i++){
            c=s[i]-'a';T.insert(c,i);
            while(1){
                if(S.ch[p][c]&&query(rt[S.ch[p][c]],l+len,r,1,n)){
                    len++;p=S.ch[p][c];
                    break;
                }
                if(len==0) break;
                if(--len==S.l[S.fa[p]]) p=S.fa[p];
            }
            T.lim[i]=len;
        }
        printf("%lld
",T.calc());
    }
    return 0;
}