【题解】CF1827C Palindrome Partition

· · 题解

【原题链接】

稍微不一样的做法。

题目分析

假设我们把一个空隙 (i,i+1) 看做一个点 i\ (0\le i\le n)，对于一个偶回文子串 s[l:r]，在点 l-1,r 之间连一条无向边。那么一个子串 [l,r] 是 beautiful 的，当且仅当存在一条 l-1\leadsto r 的路径。

那么假设能够把图建出来，答案就是对所有极大连通块 S 的 \dfrac{|S|(|S|-1)}{2} 求和。

先跑一遍 Manacher 算法，得到每个空隙 (i,i+1) 的回文半径 p_i。那么 i,i-1,\dots,i-p_i 需要分别向 i,i+1,\dots,i+p_i 连边。这个可以使用 [SCOI2016] 萌萌哒 的技巧在 O(n\log n) 的时间内解决。

代码实现

#include <bits/stdc++.h>
using namespace std;

// 省略快读

int T,n,p[500005];
char s[500005];

void manacher()
{
    static char tmp[1000005];
    static int f[1000005];
    int m=0;
    for(int i=1;i<=n;i++) tmp[++m]=s[i],tmp[++m]='#';
    tmp[0]='$',tmp[m--]='\0';
    for(int i=1,j=0,mx=0;i<=m;i++)
    {
        f[i]=0;
        if(i<mx) f[i]=min(f[j*2-i],mx-i);
        while(tmp[i-f[i]]==tmp[i+f[i]]) f[i]++;
        if(i+f[i]>mx) j=i,mx=i+f[i];
    }
    for(int i=1;i<n;i++) p[i]=f[i<<1]>>1;
}

vector<int> mdf[20];
int fa[1000005],siz[1000005],ffa[1000005];
inline void init()
{ for(int i=0;i<=2*n;i++) fa[i]=i,siz[i]=(i<=n); }
inline int findFa(int x)
{ return x!=fa[x]?fa[x]=findFa(fa[x]):x; }
inline void merge(int x,int y)
{ x=findFa(x),y=findFa(y);if(x!=y)fa[y]=x,siz[x]+=siz[y],siz[y]=0; }

int main()
{
    qin>>T;
    while(T--)
    {
        qin>>n>>(s+1);
        manacher();
        for(int i=1;i<n;i++)
            if(p[i]) mdf[__lg(p[i]+1)].push_back(i);
        iota(ffa,ffa+2*n+1,0);
        for(int k=__lg(n);k>=0;k--)
        {
            init();
            for(int i=0;i+(1<<(k+1))-1<=2*n;i++)
            {
                merge(i,ffa[i]);
                merge(i+(1<<k),ffa[i]+(1<<k));
            }
            for(auto &i: mdf[k])
            {
                int l1=i-p[i],r1=i,l2=i,r2=i+p[i];
                tie(l2,r2)=pair(2*n-r2,2*n-l2);
                merge(l1,l2);
                merge(r1-(1<<k)+1,r2-(1<<k)+1);
            }
            copy(fa,fa+2*n+1,ffa);
            mdf[k].clear();
        }
        for(int i=0;i<=n;i++) merge(i,2*n-i);
        LL ans=0;
        for(int i=0;i<=2*n;i++)
            if(findFa(i)==i) ans+=LL(siz[i])*siz[i];
        qout<<(ans-n-1)/2<<'\n';
    }
    return 0;
}