Palindrome

简要题意：

我们有一个字符串S，字符串的长度不超过500000。

求满足S[i]=S[2n−i]=S[2n+i−2](1≤i≤n)(n≥2)的子串个数。

分析：

我们能通过简单的数学知识，得到：

该子串是两个回文串拼在一起的，例如abcbabc中，前5项为一个回文串，后5项有一个回文串。

第n项以及第2*n-1项为回文串的中心。

我们可以用Manacher 求得以每个$i$为中心点的回文串半径len[i]。

求得len[i]后，写一个方程：

令i<j,

1. i+len[i]>=j;

2. j-len[j]<=i;

可以推得：

1. i+1<=j<=i+len[i];

2. j-len[j]<=i

所以，这道题便转化成：

已知一个len[i]数组，求满足上列条件的个数！

怎么求一个区间内小于一个数x的个数呢？

主席树！

主席树中记录的是每个数字出现过的个数，区间[1,5]即记录数字[1,5]出现的总次数，

我们主席树类似前缀和的思想，依次往后合并。

最终我们求得的答案为：∑query(root[i+len[i]],x)-query(root[i],x);

#include<bits/stdc++.h>

using namespace std;

#define re register int

#define LL long long

const int N=1000005;

int seg,root[N];

struct segment{int v,ls,rs;}tr[N<<4];

int build(int x,int y)

{

    int p=++seg;tr[p].v=0;

    if(x<y)

    {

        int mid=(x+y)>>1;

        tr[p].ls=build(x,mid);

        tr[p].rs=build(mid+1,y);

    }

    return p;

}

int update(int pre,int l,int r,int x)

{

    int p=++seg;

    tr[p]=(segment){tr[pre].v+1,tr[pre].ls,tr[pre].rs};

    if(l<r)

    {

        int mid=(l+r)>>1;

        if(x<=mid)tr[p].ls=update(tr[pre].ls,l,mid,x);

        else tr[p].rs=update(tr[pre].rs,mid+1,r,x);

    }

    return p;

}

int query(int p1,int p2,int l,int r,int x)

{

    if(x<l)return 0;

    if(r<=x)return tr[p1].v-tr[p2].v;

    int mid=(l+r)>>1;

    int res=query(tr[p1].ls,tr[p2].ls,l,mid,x);

    if(mid+1<=x)res+=query(tr[p1].rs,tr[p2].rs,mid+1,r,x);

    return res;

}

char S[N],s[N<<1];

int val[N<<1],pos[N];

inline void work()

{

    scanf("%s",S);int n=strlen(S);

    int k=0,id=0,mx=0;

    for(re i=0;i<n;++i)s[++k]='#',s[++k]=S[i];s[0]='!';s[++k]='#';

    for(re i=1;i<=k;++i)

    {

        if(i<mx)val[i]=min(val[id*2-i],mx-i);

        else val[i]=1;

        while(s[i-val[i]]==s[i+val[i]])val[i]++;

        if(i+val[i]>mx)mx=i+val[i],id=i;

    }

    int MAX=0;

    for(re i=2;i<=k;i+=2)

    {

        int id=(i>>1);

        pos[id]=(val[i]>>1)-1;

        MAX=max(MAX,id-pos[id]);

    }

    seg=0;root[0]=build(1,MAX);

    for(re i=1;i<=n;++i)root[i]=update(root[i-1],1,MAX,i-pos[i]);

    LL ans=0;

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

    if(pos[i])ans+=1ll*query(root[i+pos[i]],root[i],1,MAX,i);

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

}

signed main()

{

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

    while(T--)work();

}

“向前跑，迎着冷眼和嘲笑”

“失败后郁郁寡欢，那是懦夫的表现”----《追梦赤子心》

巴特西

热身训练3 Palindrome

Palindrome

最新文章

热门文章