BZOJ4516：[SDOI2016]生成魔咒——题解

时间：2023-03-09 16:43:56
BZOJ4516：[SDOI2016]生成魔咒——题解

https://www.lydsy.com/JudgeOnline/problem.php?id=4516

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。
一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。
例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。

SAM傻逼题，然而我把SAM忘光了？

没关系SAM怎么建我还记得，咦SAM怎么统计不同字符串个数来着？

于是我看了一眼BZOJ3998：[TJOI2015]弦论。

我们知道只要遍历后缀自动机就能得到所有不相同的子串，相当于每个节点有价值size=1，如果我们倒序遍历并且累加的话就能求出sum。

当然我们没必要每次都求一遍sum，我们发现我们新加入的节点，其造成的贡献按照我们上面的推论就是tr[np].l-tr[tr[np].fa].l。

（你可以试着画一个简单的后缀自动机感受一下，比如说“1231”，你就会发现实际造成贡献的就是fa~np的每个节点（除np）都由np转移来了+1，这些1需要累加到一起汇总到root，当然同理对于我们因为right集合不同而新开的点也是一样的。）

没了，很水吧。

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

#define fi first

#define se second

const int N=1e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

map<int,int>::iterator it;

struct node{

    map<int,int>a;

    int fa,l;

}tr[N<<];

int n,last,cnt;

ll ans;

inline void insert(int c){

    int p=last,np=++cnt;

    last=np;tr[np].l=tr[p].l+;

    for(;p&&!tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;

    if(!p)tr[np].fa=;

    else{

    int q=tr[p].a[c];

    if(tr[p].l+==tr[q].l)tr[np].fa=q;

    else{

        int nq=++cnt;tr[nq].l=tr[p].l+;

        for(it=tr[q].a.begin();it!=tr[q].a.end();it++)

        tr[nq].a[it->fi]=it->se;

        tr[nq].fa=tr[q].fa;tr[q].fa=tr[np].fa=nq;

        for(;tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;

    }

    }

    ans+=tr[np].l-tr[tr[np].fa].l;

}

int main(){

    n=read();

    last=cnt=;

    for(int i=;i<=n;i++){

    insert(read());printf("%lld\n",ans);

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

相关文章