[NOI2018]你的名字

☑☹☼☽✘☹™☯……☠……☺☞✄㏘☽√☺☺☺

以上是我做这题的过程

传送门

跟大家一样先说$l=1,r=n$的情况吧。

这就是求T中没有在S中出现的不同子串个数。

可以通过对$S$建后缀自动机$SAM_S$，用$T$在$SAM_S$上匹配的方法得到T每个位置的最长匹配长度。

无论去不去重，跟子串相关肯定要对$T$建$SAM_T$，那么如果不考虑重复，遍历$SAM_T$的所有节点，答案就是$\sum_{i\in SAM_T}len_i-len_{fa_i}$，这其实就是所有子串个数对吧。

然而我们对每个$i$还要减去$i$的结尾位置的匹配长度$maxn_{pos_i}$，那么就对$len_{fa_i}$和$maxn_{pos_i}$取个$max$减掉就好了，$maxn_{pos_i}$可能大于$len_i$，所以要和$0$取个$max$。

对于$l,r$任意的情况，它对我们的影响就是匹配$maxn_i$的时候可能会匹配到不在$[l,r]$里的位置，首先我们要线段树合并求出$SAM_S$每个节点的集合。

接下来的匹配比较重要我分个段。

设当前匹配长度为$len$，那么如果继续匹配，结尾的位置只能在$[l+len,r]$，所以要看看下一个节点的$endpos$集合，是不是在这个区间有值。

匹配失败是不能跳$fa$而应该减少$len$，如果$len$跳出了当前集合再跳$fa$，看起来复杂度堪忧，但因为$len$最多增加$T的长度$那么多次，而减少最多到0所以复杂度还是对的。

附上匹配代码（感觉这个比较重要）

while (1){
    if (query(root[t1[u].ch[s[i]-'a']],1,n,x+l,y)){
        l++,u=t1[u].ch[s[i]-'a']; break;
    }
    if (!l) break;
    if ((--l)==t1[t1[u].fa].len) u=t1[u].fa;
}

其实除了一些细节还算好写。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
struct SAM_S{
    int ch[26],len,fa;
}t1[1000001];
struct SAM_T{
    int ch[26],len,fa,maxn;
}t3[2000001];
struct tre{
    int ch[2];
}t2[1000001*20];
int tot_T,tot_t,tot_s=1,last_T,last=1,n,m,root[1000001];
int o[500001],a[1000001],maxn[1000001],len;
char ch[500001],s[1000001];
int update(int rt,int l,int r,int x){
    if (!rt) rt=++tot_t;
    if (l==r) return rt;
    int mid=(l+r)>>1;
    if (x<=mid) t2[rt].ch[0]=update(t2[rt].ch[0],l,mid,x);
    else t2[rt].ch[1]=update(t2[rt].ch[1],mid+1,r,x);
    return rt;
}
int merge(int c,int d,int l,int r){
    if (!c||!d) return c|d;
    int rt=++tot_t;
    if (l==r) return rt;
    int mid=(l+r)>>1;
    t2[rt].ch[0]=merge(t2[c].ch[0],t2[d].ch[0],l,mid);
    t2[rt].ch[1]=merge(t2[c].ch[1],t2[d].ch[1],mid+1,r);
    return rt;
}
bool query(int rt,int l,int r,int x,int y){
    if (!rt||x>r) return false;
    if (x<=l&&r<=y) return true;
    int mid=(l+r)>>1;
    if (x<=mid&&query(t2[rt].ch[0],l,mid,x,y)) return true;
    if (y>mid&&query(t2[rt].ch[1],mid+1,r,x,y)) return true;
    return false;
}
inline void extend_S(int x){
    int np=++tot_s,p=last; last=np;
    t1[np].len=t1[p].len+1;
    while (p&&!t1[p].ch[x]) t1[p].ch[x]=np,p=t1[p].fa;
    if (!p) t1[np].fa=1;
    else{
        int q=t1[p].ch[x];
        if (t1[q].len==t1[p].len+1) t1[np].fa=q;
        else{
            int cp=++tot_s; t1[cp]=t1[q];
            t1[cp].len=t1[p].len+1;
            t1[q].fa=t1[np].fa=cp;
            while (p&&t1[p].ch[x]==q) t1[p].ch[x]=cp,p=t1[p].fa;
        }
    }
}
inline void extend_T(int x){
    int np=++tot_T,p=last_T; last_T=np;
    t3[np].len=t3[p].len+1;
    while (p&&!t3[p].ch[x]) t3[p].ch[x]=np,p=t3[p].fa;
    if (!p) t3[np].fa=1;
    else{
        int q=t3[p].ch[x];
        if (t3[q].len==t3[p].len+1) t3[np].fa=q;
        else{
            int cp=++tot_T; t3[cp]=t3[q];
            t3[cp].len=t3[p].len+1;
            t3[q].fa=t3[np].fa=cp;
            while (p&&t3[p].ch[x]==q) t3[p].ch[x]=cp,p=t3[p].fa;
        }
    }
}
int main(){
    scanf("%s",ch+1); n=strlen(ch+1);
    for (int i=1; i<=n; i++){
        extend_S(ch[i]-'a');
        root[last]=update(root[last],1,n,i);
    }
    int u,l,x,y; ll num;
    for (int i=1; i<=tot_s; i++) o[t1[i].len]++;
    for (int i=1; i<=n; i++) o[i]+=o[i-1];
    for (int i=1; i<=tot_s; i++) a[o[t1[i].len]--]=i;
    for (int i=tot_s; i>=2; i--){
        u=a[i];
        root[t1[u].fa]=merge(root[t1[u].fa],root[u],1,n);
    }
    scanf("%d",&m);
    while (m--){
        scanf("%s",s+1); len=strlen(s+1);
        scanf("%d%d",&x,&y); u=1,l=0,num=0;
        for (int i=1; i<=len; i++) maxn[i]=0;
    if (x==1&&y==n){
        for (int i=1; i<=len; i++){
            if (t1[u].ch[s[i]-'a']) u=t1[u].ch[s[i]-'a'],l++;
            else{
                while (u&&!t1[u].ch[s[i]-'a']) u=t1[u].fa,l--;
                if (!u) u=1,l=0;
                if (t1[u].ch[s[i]-'a'])
                    l=t1[u].len+1,u=t1[u].ch[s[i]-'a'];
            }
            maxn[i]=l;
        }
    }
    else{
        for (int i=1; i<=len; i++){
            if (t1[u].ch[s[i]-'a']&&query(root[t1[u].ch[s[i]-'a']],1,n,x+l,y))
                u=t1[u].ch[s[i]-'a'],l++;
            else{
                while (1){
                    if (query(root[t1[u].ch[s[i]-'a']],1,n,x+l,y)){
                        l++,u=t1[u].ch[s[i]-'a']; break;
                    }
                    if (!l) break;
                    if ((--l)==t1[t1[u].fa].len) u=t1[u].fa;
                }
                // if (u) l++,u=t1[u].ch[s[i]-'a'];
                // else u=1,l=0;
            }
            maxn[i]=l;
        }
    }
        tot_T=last_T=1;
        for (int i=1; i<=len; i++)
            extend_T(s[i]-'a'),t3[last_T].maxn=maxn[i];
        for (int i=2; i<=tot_T; i++)
            num+=max(0,t3[i].len-max(t3[t3[i].fa].len,t3[i].maxn));
        printf("%lld\n",num);
        for (int i=1; i<=tot_T; i++) t3[i]=t3[0];
    }
    return 0;
}