19_07_11校内训练[字串染色]

àì夳堔傛蜴生んèń 2021-10-19 04:20 233阅读 0赞

# 题意 #

定义一个字符串某个子串的价值为：将其所有出现的位置染成黑色后，黑色连续段的个数。问有多少本质不同的子串，价值恰好为K。n,K<=1E5。

--------------------

# 思考 #

由本质不同的字符串，考虑SAM维护。对于SAM上的一个节点，其endpos集合代表了字符串中的一些位置。设这些位置相邻的距离的集合为dis，则对于这个节点而言，某个子串的价值为(endpos集合的大小-这个子串的长度>=disi的个数)。由于一个节点的包含的字符串长度是连续的，可以很快地算出这个节点的贡献。

这样一来，只要维护距离的集合即可。可以维护endpos集合、距离区间集合、距离长度的多重集。前两个用set即可，第三个用splay。按秩合并，总复杂度O(nlongn^2)。

另外，还要注意endpos大小小于等于k的情况，以及有相同距离的情况。

--------------------

# 代码 #

其中spaly占了一半的代码。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #pragma GCC optimize 2
      2 #include<bits/stdc++.h>
      3 using namespace std;
      4 const int maxn=2E5+5;
      5 string str;
      6 int n,K,ans;
      7 int head[maxn*2],size;
      8 int bel[maxn],len[maxn],another[maxn];
      9 set<int>endpos[maxn];
     10 struct line
     11 {
     12     int l,r;
     13     line(int a=0,int b=0)
     14     {
     15         l=a,r=b;
     16     }
     17     bool operator<(const line&A)const
     18     {
     19         return l==A.l?r<A.r:l<A.l;
     20     }
     21     bool operator<=(const line&A)const
     22     {
     23         return l==A.l?r<=A.r:l<=A.l;
     24     }
     25 };
     26 set<line>gap[maxn];
     27 struct node
     28 {
     29     int fa,len,ch[26];
     30 };
     31 struct edge
     32 {
     33     int to,next;
     34 }E[maxn*2];
     35 inline void add(int u,int v)
     36 {
     37     E[++size].to=v;
     38     E[size].next=head[u];
     39     head[u]=size;
     40 }
     41 ////
     42 int faT[maxn*2],son[maxn*2][2],sumT[maxn*2],valT[maxn*2],times[maxn*2];
     43 int totT;
     44 struct Splay
     45 {
     46     int root;
     47     Splay()
     48     {
     49         root=0;
     50     }
     51     inline void update(int x)
     52     {
     53         sumT[x]=sumT[son[x][0]]+sumT[son[x][1]]+times[x];
     54     }
     55     bool empty()
     56     {
     57         return root==0;
     58     }
     59     inline void rotate(int x,int c)
     60     {
     61         int y=faT[x];
     62         faT[x]=faT[y];
     63         son[y][!c]=son[x][c];
     64         if(son[x][c])faT[son[x][c]]=y;
     65         if(son[faT[y]][0]==y)son[faT[y]][0]=x;
     66         else son[faT[y]][1]=x;
     67         son[x][c]=y;
     68         faT[y]=x;
     69         if(y==root)
     70             root=x;
     71         update(y),update(x); 
     72     }
     73     void splay(int x,int to)
     74     {
     75         while(true)
     76         {
     77             if(faT[x]==0||x==root)
     78                 break;
     79             int y=faT[x];
     80             if(y==to)
     81             {
     82                 if(son[y][0]==x)rotate(x,1);
     83                 else rotate(x,0);
     84                 break;
     85             }
     86             if(faT[y]==to)
     87             {
     88                 if(son[faT[y]][0]==y)
     89                 {
     90                     if(son[y][0]==x)rotate(x,1),rotate(x,1);
     91                     else rotate(x,0),rotate(x,1);
     92                 }
     93                 else
     94                 {
     95                     if(son[y][1]==x)rotate(x,0),rotate(x,0);
     96                     else rotate(x,1),rotate(x,0);
     97                 }
     98                 return;
     99             }
    100             if(son[faT[y]][0]==y)
    101             {
    102                 if(son[y][0]==x)rotate(y,1),rotate(x,1);
    103                 else rotate(x,0),rotate(x,1);
    104             }
    105             else
    106             {
    107                 if(son[y][1]==x)rotate(y,0),rotate(x,0);
    108                 else rotate(x,1),rotate(x,0);
    109             }
    110         }
    111     }
    112     void addNode(int pos,int c,int x)
    113     {
    114         son[pos][c]=++totT;
    115         faT[totT]=pos;
    116         valT[totT]=x;
    117         sumT[totT]=times[totT]=1;
    118     }
    119     void insert(int x)
    120     {
    121         if(root==0){valT[++totT]=x;times[totT]=1;root=totT;update(root);return;}
    122         int pos=root;
    123         while(true)
    124         {
    125             if(x==valT[pos]){++times[pos],++sumT[pos];break;}
    126             else if(x<valT[pos])
    127             {
    128                 ++sumT[pos];
    129                 if(son[pos][0])pos=son[pos][0];
    130                 else{addNode(pos,0,x);pos=totT;break;}
    131             }
    132             else
    133             {
    134                 ++sumT[pos];
    135                 if(son[pos][1])pos=son[pos][1];
    136                 else{addNode(pos,1,x);pos=totT;break;}
    137             }
    138         }
    139         splay(pos,root);
    140     }
    141     int ask(int x)
    142     {
    143         if(root==0)
    144             return 0;
    145         int pos=root,where=-1;
    146         while(pos)
    147         {
    148             if(valT[pos]>=x)pos=son[pos][0];
    149             else where=pos,pos=son[pos][1];
    150         }
    151         if(where==-1)return 0;
    152         pos=where;
    153         splay(pos,root);
    154         return sumT[son[pos][0]]+times[pos];
    155     }
    156     int rkSmall(int x)
    157     {
    158         int pos=root;
    159         while(x)
    160         {
    161             if(sumT[son[pos][0]]>=x)
    162                 pos=son[pos][0];
    163             else if(sumT[son[pos][0]]+times[pos]>=x)
    164                 break;
    165             else
    166                 x-=sumT[son[pos][0]]+times[pos];
    167         }
    168         splay(pos,root);
    169         return valT[pos];
    170     }
    171     int rkBig(int x)
    172     {
    173         return rkSmall(sumT[root]-x+1);
    174     }
    175     inline int nxt(int pos)
    176     {
    177         while(son[pos][1])
    178             pos=son[pos][1];
    179         return pos;
    180     }
    181     inline int pre(int pos)
    182     {
    183         while(son[pos][0])
    184             pos=son[pos][0];
    185         return pos;
    186     }
    187     void remove(int x)
    188     {
    189         assert(root!=0);
    190         int pos=root;
    191         while(pos)
    192             if(valT[pos]==x)break;
    193             else if(x<valT[pos])pos=son[pos][0];
    194             else pos=son[pos][1];
    195         assert(pos!=0);
    196         splay(pos,root);
    197         if(times[pos]>=2)
    198         {
    199             --times[pos],--sumT[pos];
    200             return;
    201         }
    202         else if(!son[pos][0]&&!son[pos][1])
    203         {
    204             times[pos]=sumT[pos]=valT[pos]=root=0;
    205         }
    206         else if(son[pos][0]&&!son[pos][1])
    207         {
    208             int pos1=nxt(son[pos][0]);
    209             splay(pos1,root);
    210             faT[pos]=son[pos1][1]=0;
    211             times[pos]=sumT[pos]=valT[pos]=0;
    212             update(pos1);
    213         }
    214         else if(!son[pos][0]&&son[pos][1])
    215         {
    216             int pos2=pre(son[pos][1]);
    217             splay(pos2,root);
    218             faT[pos]=son[pos2][0]=0;
    219             times[pos]=sumT[pos]=valT[pos]=0;
    220             update(pos2);
    221         }
    222         else
    223         {
    224             int pos1=nxt(son[pos][0]),pos2=pre(son[pos][1]);
    225             splay(pos1,root);
    226             splay(pos2,pos);
    227             faT[pos]=son[pos2][0]=0;
    228             times[pos]=sumT[pos]=valT[pos]=0;
    229             update(pos2),update(pos1);
    230         }
    231     }
    232     void out()
    233     {
    234         cout<<"i    :";for(int i=1;i<=totT;++i)cout<<i<<" ";cout<<endl;
    235         cout<<"faT  :";for(int i=1;i<=totT;++i)cout<<faT[i]<<" ";cout<<endl;
    236         cout<<"valT :";for(int i=1;i<=totT;++i)cout<<valT[i]<<" ";cout<<endl;
    237         cout<<"son  :";for(int i=1;i<=totT;++i)cout<<son[i][0]<<" ";cout<<endl;
    238         cout<<"     :";for(int i=1;i<=totT;++i)cout<<son[i][1]<<" ";cout<<endl;
    239         cout<<"sumT :";for(int i=1;i<=totT;++i)cout<<sumT[i]<<" ";cout<<endl;
    240     }
    241 }dis[maxn*2];
    242 ////
    243 struct SAM
    244 {
    245     node t[maxn*2];
    246     int tot,last;
    247     SAM()
    248     {
    249         tot=last=1;
    250     }
    251     void insert(int x,int id)
    252     {
    253         int u=last,now=++tot;
    254         t[now].len=t[last].len+1;
    255         last=tot;
    256         another[now]=id;
    257         bel[now]=now;
    258         for(;u&&!t[u].ch[x];u=t[u].fa)
    259             t[u].ch[x]=tot;
    260         if(!u)
    261             t[now].fa=1;
    262         else
    263         {
    264             int v=t[u].ch[x];
    265             if(t[u].len+1==t[v].len)
    266                 t[now].fa=v;
    267             else
    268             {
    269                 int w=++tot;
    270                 t[w]=t[v];
    271                 t[w].len=t[u].len+1;
    272                 t[v].fa=t[now].fa=w;
    273                 for(;u&&t[u].ch[x]==v;u=t[u].fa)
    274                     t[u].ch[x]=w;
    275             }
    276         }
    277     }
    278     void build()
    279     {
    280         for(int u=2;u<=tot;++u)
    281         {
    282             add(t[u].fa,u);
    283             len[u]=t[u].len;
    284         }
    285     }
    286 }T;
    287 void out(set<line>S)
    288 {
    289     for(set<line>::iterator pt=S.begin();pt!=S.end();++pt)
    290         cout<<"("<<(*pt).l<<","<<(*pt).r<<") ";
    291     cout<<endl;
    292 }
    293 void change(int u,int val)
    294 {
    295     set<int>::iterator pR=endpos[bel[u]].upper_bound(val);
    296     if(endpos[bel[u]].size()==0);
    297     else if(pR==endpos[bel[u]].end())
    298     {    
    299         --pR;
    300         gap[bel[u]].insert(line(*pR,val));
    301         dis[bel[u]].insert((val)-(*pR));
    302     }
    303     else if(pR==endpos[bel[u]].begin())
    304     {
    305         gap[bel[u]].insert(line(val,*pR));
    306         dis[bel[u]].insert((*pR)-(val));
    307     }
    308     else
    309     {
    310         set<int>::iterator pL=endpos[bel[u]].upper_bound(val);
    311         --pL;
    312         line x(*pL,*pR);
    313         dis[bel[u]].remove(x.r-x.l);
    314         gap[bel[u]].erase(gap[bel[u]].lower_bound(x));
    315         gap[bel[u]].insert(line(*pL,val));
    316         gap[bel[u]].insert(line(val,*pR));
    317         dis[bel[u]].insert((val)-(*pL));
    318         dis[bel[u]].insert((*pR)-(val));
    319     }
    320     endpos[bel[u]].insert(val);
    321 }
    322 void dfs(int u,int F)
    323 {
    324     int num=u,g=0;
    325     for(int i=head[u];i;i=E[i].next)
    326     {
    327         int v=E[i].to;
    328         dfs(v,u);
    329         if(endpos[bel[v]].size()>g)
    330             g=endpos[bel[v]].size(),num=v;
    331     }
    332     bel[u]=bel[num];
    333     if(another[u])
    334         change(u,another[u]);
    335     for(int i=head[u];i;i=E[i].next)
    336     {
    337         int v=E[i].to;
    338         if(bel[u]==bel[v])
    339             continue;
    340         for(set<int>::iterator pt=endpos[bel[v]].begin();pt!=endpos[bel[v]].end();++pt)
    341             change(u,*pt);
    342     }
    343     /*
    344     cout<<u<<" : ";
    345     for(set<int>::iterator pt=endpos[bel[u]].begin();pt!=endpos[bel[u]].end();++pt)
    346         cout<<*pt<<" ";
    347     cout<<"| "<<len[u]<<" "<<len[F]+1<<endl;
    348     out(gap[bel[u]]);
    349     outQ(dis[bel[u]]);
    350     cout<<ans<<endl;
    351     cout<<endl;
    352     */
    353     if(endpos[bel[u]].size()<=K)
    354     {
    355         if(endpos[bel[u]].size()==K)
    356             if(K==1)
    357                 ans+=len[u]-len[F];
    358             else
    359                 ans+=max(0,min(len[u],dis[bel[u]].rkSmall(1)-1)-len[F]);
    360         return;
    361     }
    362     if(K==1)
    363     {
    364         int d=dis[bel[u]].rkBig(K);
    365         ans+=max(0,len[u]-max(d,len[F]+1)+1);
    366     }
    367     else
    368     {
    369         int d=dis[bel[u]].rkBig(K);
    370         int D=dis[bel[u]].rkBig(K-1);
    371         if(d!=D)
    372             ans+=max(0,len[u]-max(d,len[F]+1)+1);
    373     }
    374 }
    375 int main()
    376 {
    377     ios::sync_with_stdio(false);
    378     cin>>str>>K;
    379     n=str.size();
    380     str="!"+str;
    381     for(int i=1;i<=n;++i)
    382         T.insert(str[i]-'a',i);
    383     T.build();
    384     dfs(1,0);
    385     cout<<ans<<endl;
    386     return 0;
    387 }

转载于:https://www.cnblogs.com/GreenDuck/p/11174756.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/1d78d546ea684c0fbb2f439072fd802b.png