bzoj4516: [Sdoi2016]生成魔咒 sam

时间：2023-03-08 20:40:15
bzoj4516: [Sdoi2016]生成魔咒 sam

题意:每次插入一个数字,查询本质不同的子串有多少个

题解:sam,数字很大,ch数组用map来存,每次ins之后查询一下新建点表示多少个本质不同的子串(l[np]-l[fa[np]])

/**************************************************************

    Problem: 4516

    User: walfy

    Language: C++

    Result: Accepted

    Time:804 ms

    Memory:16600 kb

****************************************************************/

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

//#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

template<typename T>

inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>

inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=100000+10,maxn=100000+10,inf=0x3f3f3f3f;

char s[N];

ll ans=0;

struct SAM{

    int last,cnt;

    int fa[N<<1],l[N<<1];

    map<int,int>ch[N<<1];

    int c[N<<1],a[N<<1];

    void ins(int c){

        int p=last,np=++cnt;last=np;l[np]=l[p]+1;

        for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;

        if(!p)fa[np]=1;

        else

        {

            int q=ch[p][c];

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

            else

            {

                int nq=++cnt;l[nq]=l[p]+1;

                ch[nq]=ch[q];

//                memcpy(ch[nq],ch[q],sizeof(ch[q]));

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

                for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;

            }

        }

        ans+=1ll*(l[np]-l[fa[np]]);

    }

    void build(){

        last=cnt=1;

    }

}sam;

int main()

{

    sam.build();

    int n;scanf("%d",&n);

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

    {

        int x;scanf("%d",&x);

        sam.ins(x);

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

    }

    return 0;

}

/********************

********************/

相关文章