HDU 4641 K-string 后缀自动机 并查集

http://acm.hdu.edu.cn/showproblem.php?pid=4641

https://blog.****.net/asdfgh0308/article/details/40969047

给一个小写字母字符串，1 a表示在字符串尾部添加一个小写字母a，2 表示当前有多少种子串出现次数大于等于K。

求出现次数桶排序（说是拓扑排序也可以？）就阔以了，种类就是t[i].len-t[t[i].f].len。

在线处理是直接扫描，时间复杂度是O(树高*m)。

离线做法是先把所有添加操作都做完，然后去掉字母反向求子串种数，可以使用并查集降低时间复杂度（每个连通块中只有总父亲表示的子串对当前答案有贡献，保证了每个点的平均扫描次数）。

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<cmath>
 #include<queue>
 using namespace std;
 #define LL long long
 const int maxn=;
 int n,m,K;
 char ch[maxn*],ch1[];
 int e[maxn*]={},b[maxn*]={},siz;
 struct nod{
     int sig[],f,len;
 }t[maxn*]; int tot,la;

 int cnt[maxn*]={},rk[maxn*]={};
 int fa[maxn*]={},sub[maxn*]={},g[maxn*]={};
 LL ans[maxn*]={};

 void addit(int z){
     int x=++tot,i=la; t[x].len=t[i].len+;
     b[siz]=x;
     for(;i&&!t[i].sig[z];i=t[i].f)t[i].sig[z]=x;
     if(!i)t[x].f=;
     else{
         int y=t[i].sig[z];
         if(t[y].len==t[i].len+)t[x].f=y;
         else{
             int p=++tot;
             t[p]=t[y];t[p].len=t[i].len+;
             t[y].f=t[x].f=p;
             for(;i&&t[i].sig[z]==y;i=t[i].f)t[i].sig[z]=p;
         }
     }
     la=x;
 }
 void msort(){
     int i;
     for(i=;i<=siz;i++)cnt[i]=;
     for(i=;i<=tot;i++)cnt[t[i].len]++;
     for(i=;i<=siz;i++)cnt[i]+=cnt[i-];
     for(i=tot;i>;i--)rk[cnt[t[i].len]--]=i;
 }
 int getfa(int x){
     int y=x,z;
     while(y!=fa[y])y=fa[y];
     while(x!=fa[x]){ z=x; x=fa[x];fa[z]=y;}
     return fa[x];
 }
 int main(){
     int i,p,y; LL num;
     while(~scanf("%d%d%d",&n,&m,&K)){
         memset(t,,sizeof(t)); tot=; la=; siz=;
         scanf("%s",ch);
         for(i=;i<n;++i){ addit(ch[i]-'a'); ++siz; }
         for(i=;i<=m;i++){
             scanf("%d",&e[i]);
             if(e[i]==){ scanf("%s",ch1); addit(ch1[]-'a'); ch[siz++]=ch1[]; }
         }
         msort(); p=,num=;
         for(i=;i<=tot;i++){ g[i]=; fa[i]=i; sub[i]=;}
         for(i=;i<siz;++i){ p=t[p].sig[ch[i]-'a']; ++g[p]; }
         for(i=tot-;i>;i--){ p=rk[i]; if(t[p].f!=)g[t[p].f]+=g[p]; }
         for(i=;i<=tot;++i){ if(g[i]>=K) num+=t[i].len-t[t[i].f].len; }
         for(i=m;i>;i--){
             if(e[i]==)ans[i]=num;
             else{
                 p=b[--siz];
                 y=getfa(p);
                 while(y!=&&g[y]<K){ fa[y]=getfa(t[y].f); y=fa[y];}
                 y=getfa(p);
                 if(y==)continue;
                 sub[y]++;
                 while(y!=&&(g[y]-sub[y]<K)){
                     num-=t[y].len-t[t[y].f].len;
                     p=getfa(t[y].f);
                     sub[p]+=sub[y]; fa[y]=p;
                     y=fa[y];
                 }
             }
         }
         for(i=;i<=m;++i)if(e[i]==)printf("%lld\n",ans[i]);
     }
     return ;
 }