[NOI2018] 你的名字

Description

给定字符串 s 。有 $q$ 个询问，每个询问形如 $t\ l\ r$ ，表示查询字符串 t 中有多少个本质不同的子串在 s[l:r] 中没出现过。
$q,|s|,|t|\leq 5\times 10^5$

Solution

将问题拆为两个部分：
（1）t 中本质不同的子串
（2）在 s[l:r] 中没出现过的子串

去重的第一想法是对于两个在 t 串中完全相同的子串，仅在第一次出现位置计算贡献。这个想法往往会因为难以找到判断是否是第一次出现而被摒弃。但是，在此题中这个想法是实用的。去重的工作可以由 SAM 实现，找到第一次出现的位置也可以通过在 parent 树上上传标记实现。
子串可以视作原串一段前缀的后缀。对于一个串，我们不仅找到其第一次出现位置，更加具体地，我们把它的贡献计算在第一次出现位置的末尾位置 $i$ 上，也就是算作 t[1:i] 这段前缀的贡献。
此时有一个重要结论：

若 $j$ 为最大的满足 t[j:i] 的贡献计入 t[1:i] 这段前缀的贡献的位置，那么 $\forall k\in [1,j]$ ，t[k:i] 的贡献均计入 t[1:i] 这段前缀中。

也就是满足 t[j:i] 在 t[1:i] 造成贡献的 $j$ 一定是从 $1$ 开始连续的一段。毕竟如果存在一个位置 $p(p\in[1,j))$ 的贡献计入别处 t[1:k] 的话，就说明 $k$ 一定小于 $i$ 。那么 t[p:i] 的所有子串都可以计入 t[1:k] 上。于是假设不成立，结论正确。
有了上述结论，我们只需要对于 t的每个位置 $i$ ，记录最大的 $j$ 满足 t[i:j] 的贡献计入 $i$ 的 $j$ 就行了。

接着考虑如何找在 s[l:r] 中没出现过的子串。对 s 建 SAM ，并利用动态开点版的线段树合并维护 SAM 上每个节点的 endpos 集合。此时，我们已经可以判定某个长度为 len 的串是否在 s[l:r] 中出现了——找到对应的节点，并在该点的线段树上查询 $[l+\text{len}-1,r]$ 内是否有一个 endpos 。
用 t 串来匹配 s 串。固定右端点 $R$ ，找到最远的，满足 t[L:R] 在 s 中出现过的 $L$ 。于是可以发现对于固定的右端点 $R$ 而言，不满足 t[L:R] 在 s 中出现过的 $L$ 恰好也是一段前缀！也就是说，如果我们能找到这个 $L$ ，那么就只需要与上面计入贡献的那个 $j$ 取 min 就行了。
怎么在 SAM 上匹配字符串呢？考虑跳 link 边本质上是丢弃一段已匹配的前缀。当现有的前缀无法满足加入第 $R+1$ 个字母的需求时，我们不妨丢弃一段前缀，剩下的后缀更加灵活，更有可能允许加入第 $R+1$ 个字符。故我们能接就接，不能接就跳 link 。需要注意的是，本题中的匹配只允许在 s[l:r] 中找，当这个区间中没有转移后的字符串时，我们也必须再跳 link 。

有一个小细节：尽管我在叙述时用的是跳 link ，但实际并非如此。 SAM 上的一个节点维护了若干个字符串，也许当丢弃了一段前缀后的字符串仍然在该节点中，此时无需跳 link 边。务必要小心。

对于一个 $R$ ，前后两次求出来的 $L$ 取 min 即为该位置上的答案。

时间复杂度 $\mathcal{O}(|s|\log_2{|s|})$ 。

Code

实现的有点丑陋... 第一次写码农字符串题🤢...

const int N=1e6+5;
using namespace std;
namespace SEG{
#define mid (l+r>>1)
#define ls c[p][0],l,mid
#define rs c[p][1],mid+1,r
    int tot;
    int t[N<<5],c[N<<5][2];
    void modify(int &p,int l,int r,int pos){
        p=++tot;t[p]=1;
        if(l==r) return void();
        if(pos<=mid) modify(ls,pos);
        else modify(rs,pos);
    }
    void merge(int &p,int x,int l,int r){
        if(p==0||x==0) return p=x+p,void();
        int cur=++tot;
        t[cur]=t[p]+t[x],c[cur][0]=c[p][0],c[cur][1]=c[p][1];
        p=cur;
        if(l==r) return;
        merge(c[p][0],c[x][0],l,mid);
        merge(c[p][1],c[x][1],mid+1,r);
    }
    int query(int p,int l,int r,int nl,int nr){
        if(l>=nl&&r<=nr) return t[p];
        int ret=0;
        if(mid>=nl) ret+=query(ls,nl,nr);
        if(mid< nr) ret+=query(rs,nl,nr);
        return ret; 
    }
    void print(int p,int l,int r){
        if(l==r) printf("%d ",l);
        if(t[c[p][0]]) print(ls);
        if(t[c[p][1]]) print(rs);
    }
}
namespace SAM1{
    int t[N],A[N],rk[N],rt[N];
    int las,tot,len;
    struct SAM{
        int l,link,c[26];
    }a[N];
    void insert(int k,int i){
        int p=las,cur=las=++tot;SEG::modify(rt[cur],1,len,i);
        a[cur].l=a[p].l+1;
        while(p&&!a[p].c[k]) a[p].c[k]=cur,p=a[p].link;
        if(p==0) return a[cur].link=1,void();
        int q=a[p].c[k];
        if(a[q].l==a[p].l+1) return a[cur].link=q,void();
        int now=++tot;
        a[now]=a[q];a[now].l=a[p].l+1,a[cur].link=a[q].link=now;
        while(p&&a[p].c[k]==q) a[p].c[k]=now,p=a[p].link;
    }
    void basesort(){
        for(int i=1;i<=tot;++i) ++t[a[i].l];
        for(int i=1;i<=len;++i) t[i]+=t[i-1];
        for(int i=1;i<=tot;++i) rk[t[a[i].l]--]=i;
    }
    void solve(char *s){
        las=tot=1;
        len=strlen(s+1);
        for(int i=1;i<=len;++i)
            insert(s[i]-'a',i);
        basesort();
        for(int i=tot;i>=2;--i){
            int u=rk[i];
            SEG::merge(rt[a[u].link],rt[u],1,len);
        }
    }
    void match(char *s,int l,int r){
        int leng=strlen(s+1),L=1,R=0;
        for(int i=1,u=1;i<=leng;++i){
            while((L<=R)&&!SEG::query(rt[a[u].c[s[i]-'a']],1,len,l+(R-L+1),r)){
                ++L;
                if(a[u].link&&a[a[u].link].l>=R-L+1)
                    u=a[u].link;
            }
            if(SEG::query(rt[a[u].c[s[i]-'a']],1,len,l+(R-L+1),r)) 
                u=a[u].c[s[i]-'a'];
            else ++L;
            A[++R]=L-1;
        }
    }
}
namespace SAM2{
    int t[N],B[N],rk[N],pos[N];
    int las,tot,len;
    struct SAM{
        int l,link,c[26];
    }a[N];
    void reset (int p){
        memset(a[p].c,0,sizeof a[p].c);
        a[p].link=a[p].l=0;
    }
    void insert(int k){
        int p=las,cur=las=++tot;reset(tot);
        a[cur].l=a[p].l+1;
        while(p&&!a[p].c[k]) a[p].c[k]=cur,p=a[p].link;
        if(p==0) return a[cur].link=1,void();
        int q=a[p].c[k];
        if(a[q].l==a[p].l+1) return a[cur].link=q,void();
        int now=++tot;reset(tot);
        a[now]=a[q];a[now].l=a[p].l+1,a[cur].link=a[q].link=now;
        while(p&&a[p].c[k]==q) a[p].c[k]=now,p=a[p].link;
    }
    void basesort(){
        for(int i=1;i<=tot;++i) ++t[a[i].l];
        for(int i=1;i<=len;++i) t[i]+=t[i-1];
        for(int i=1;i<=tot;++i) rk[t[a[i].l]--]=i;
        for(int i=1;i<=tot;++i) t[a[i].l]=0; 
    }
    void solve(char *s){
        las=tot=1;reset(1);
        len=strlen(s+1);
        for(int i=1;i<=len;++i)
            insert(s[i]-='a');
        for(int i=1;i<=tot;++i) pos[i]=0x3f3f3f3f;
        for(int i=1,u=1;i<=len;++i){
            u=a[u].c[int(s[i])];
            pos[u]=i;
            B[i]=0x3f3f3f3f;
        }
        basesort();
        for(int i=tot,u=rk[i];i>=1;--i,u=rk[i])
            pos[a[u].link]=min(pos[a[u].link],pos[u]);
        for(int i=1,u=rk[i];i<=tot;++i,u=rk[i])
            B[pos[u]]=min(B[pos[u]],a[a[u].link].l);
        for(int i=1;i<=len;++i)
            B[i]=i-B[i];
    }
}