Prutekoi's blog

看到这道题我的做法踩了大多数人,我就来写个题解。
题意:

维护一个串,初始为空,支持往末尾插字符删字符,每次操作后询问本质不同的子串个数。

这道题如果只支持插入操作的话就是[SDOI2016]生成魔咒。
而删除字符相当于撤回了一次操作,看到这种支持撤回操作的问题很容易想到操作树。而我们把这棵操作树建出来以后它其实就是trie。那么我们在trie上遍历维护后缀自动机,就变成生成魔咒这道题了,进子树时插入字符,出子树时撤销影响,复杂度是$O(n)$的。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+50;
int n,ch[N][26],tot,f[N],trans[N][26],par[N],mxlen[N],cnt=1,lst=1,tp;char s[N];LL anss,ans[N];
vector<int>v[N];
struct node{int x,tr,pa;}st[N*5];
void extend(int c){
    int cur=++cnt,p=lst;mxlen[cur]=mxlen[p]+1;
    for(;p&&!trans[p][c];p=par[p])trans[p][c]=cur,st[++tp]=(node){p,0,par[p]};
    if(!p)par[cur]=1;
    else{
        int q=trans[p][c];
        if(mxlen[q]==mxlen[p]+1)par[cur]=q;
        else{
            int nq=++cnt;
            memcpy(trans[nq],trans[q],sizeof(trans[q]));
            mxlen[nq]=mxlen[p]+1;par[nq]=par[q];
            for(;p&&trans[p][c]==q;p=par[p])trans[p][c]=nq,st[++tp]=(node){p,q,par[p]};
            st[++tp]=(node){q,trans[q][c],par[q]};par[cur]=par[q]=nq;
        }
    }
    lst=cur;
}
void dfs(int x){
    for(int i=0;i<v[x].size();i++)ans[v[x][i]]=anss;
    for(int i=0;i<26;i++)if(ch[x][i]){
        int dat=cnt,tt=tp,ll=lst;LL aa=anss;
        extend(i);anss+=mxlen[lst]-mxlen[par[lst]];dfs(ch[x][i]);
        anss=aa;lst=ll;
        while(cnt>dat)memset(trans[cnt],0,sizeof(trans[cnt])),cnt--;
        while(tp>tt)trans[st[tp].x][i]=st[tp].tr,par[st[tp].x]=st[tp].pa,tp--;
    }
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1,p=0;i<=n;i++){
        if(s[i]=='-')p=f[p];
        else{
            int c=s[i]-'a';
            if(!ch[p][c])f[ch[p][c]=++tot]=p;
            p=ch[p][c];
        }
        v[p].push_back(i);
    }
    dfs(0);
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}

网上的题解好像全都是广义SAM+set,我也搞不懂233