并不对劲的bzoj4650:loj2083:uoj219:p1117:[NOI2016]优秀的拆分

题目大意

“优秀的拆分”指将一个字符串拆分成AABB的形式

十次询问，每次给出一个字符串S（\(|S|\leq3*10^4\)），求它的所有子串的优秀的拆分的方案数之和

题解

此题过于优秀，题解先坑着

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];k!=-1;k=nxt[k])

#define maxn 30010

#define LL long long

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(LL x)

{

    if(x==0){putchar('0'),putchar('\n');return;}

    int f=0;char ch[20];

    if(x<0)putchar('-'),x=-x;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

    return;

}

int t,n,a[2][maxn];

LL ans;

char s[maxn];

void add(int l,int r,int f){if(l<=r)a[f][l]++,a[f][r+1]--;}

void geta(){rep(i,1,n)a[0][i]+=a[0][i-1],a[1][i]+=a[1][i-1];return;}

struct SAM

{

    int ch[maxn<<1][26],rt,lst,cnt,dis[maxn<<1],fa[maxn<<1],pos[maxn],tim,dfn[maxn<<1],st[20][maxn<<2],lg[maxn<<2],len;

    int fir[maxn<<1],nxt[maxn<<1],v[maxn<<1],cnte,dep[maxn<<1];

    char s[maxn];

    void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}

    int gx(char c){return c-'a';}

    void ext(int id)

    {

        int p=lst,np=++cnt,val=gx(s[id]);dis[np]=id,pos[id]=np,lst=np;

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

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

        else

        {

            int q=ch[p][val];

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

            else

            {

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

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

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

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

            }

        }

    }

    void dfs(int u)

    {

        dfn[u]=++tim,st[0][tim]=u;

        view(u,k){dep[v[k]]=dep[u]+1,dfs(v[k]),st[0][++tim]=u;}

    }

    int lcs(int x,int y)

    {

        x=dfn[pos[x]],y=dfn[pos[y]];

        if(x>y)swap(x,y);

        int len=y-x+1;

        return dis[dep[st[lg[len]][x]]<dep[st[lg[len]][y-(1<<lg[len])+1]]?st[lg[len]][x]:st[lg[len]][y-(1<<lg[len])+1]];

    }

    void build()

    {

        rt=lst=cnt=1;

        rep(i,1,len)ext(i);

        rep(i,1,cnt)fir[i]=-1;

        rep(i,1,cnt)ade(fa[i],i);lg[0]=-1;

        dfs(rt);

        rep(i,1,tim)lg[i]=lg[i>>1]+1;

        rep(k,1,lg[tim])for(int i=1;i+(1<<k)-1<=tim;i++)

            st[k][i]=dep[st[k-1][i]]<dep[st[k-1][i+(1<<(k-1))]]?st[k-1][i]:st[k-1][i+(1<<(k-1))];

    }

    void reset()

    {

        rep(i,1,cnt){dep[i]=fa[i]=dis[i]=dfn[i]=0;rep(j,0,25)ch[i][j]=0;}

        rep(i,1,tim)st[0][i]=0;tim=cnt=rt=cnte=lst=0;

    }

}pre,suf;

int main()

{

    t=read();

    while(t--)

    {

        scanf("%s",s+1);

        n=strlen(s+1);ans=0;

        rep(i,1,n)pre.s[i]=s[i],suf.s[i]=s[n-i+1];pre.len=suf.len=n;

        pre.build(),suf.build();

        rep(len,1,(n>>1))

        {

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

            {

                int lp=pre.lcs(i,i+len),ls=suf.lcs(n-i+1,n-(i+len)+1);

                if(lp+ls>len)add(max(i-len+1,i-lp+1),min(i,i+ls-len),1),add(max(i+len,i-lp+(len<<1)),min(i+len+len-1,i+len+ls-1),0);

            }

        }

        geta();

        rep(i,1,n-1)ans+=(LL)a[0][i]*(LL)a[1][i+1];

        rep(i,0,n+1)a[0][i]=a[1][i]=0;pre.reset(),suf.reset();

        write(ans);

    }

    return 0;

}

/*

4

aabbbb

cccccc

aabaabaabaa

bbaabaababaaba

*/

巴特西

并不对劲的bzoj4650:loj2083:uoj219:p1117:[NOI2016]优秀的拆分

题目大意

题解

代码

最新文章

热门文章