CF356E Xenia and String Problem

英文题面

题意：给定一个字符串\(S\)。定义一个字符串\(t\)是"gray"串，当且仅当：

• \(|t|\)是奇数；
• 设\(mid=(1+|t|)/2\)，则\(t_{mid}\)仅在\(t\)中出现一次；
• \(t_{1,\cdots mid-1}\)和\(t_{mid+1,\cdots |t|}\)相同，且都为gray串。

定义一个串\(t\)的美丽度为：\(\sum_{l,r} (r-l+1)^2 \times [t_{l,\cdots r}是gray串]\)。

你可以修改\(S\)的一个字符，当然也可以不修改。求修改后的\(S\)的美丽度的最大值。

题解：

设\(n=|S|\)。考虑到gray串的长度为\(2^k -1\)，所以gray串的总数是\(nlogn\)级别的。

先考虑如何求出所有的gray串。我们可以做一个类似求st表的东西，设\(g_{i,j}\)表示以\(i\)为左端点，长度为\(2^j -1\)的串是否为gray串。可以通过字符串哈希或者后缀数组求得两边的串是否相同。然后对于第二个限制，记一个前缀和数组\(s_{i,j}\)表示字符\(j\)在\([1,i]\)中的出现次数就行了。

再考虑改变一个字符对美丽度的影响。我们可以看作是将其删除，然后再加入。删除的过程中，所有包含当前点的子串的贡献都需要被减去。这个只需要开一个数组，在算上面的东西的同时维护一下。由于是区间加，用差分就好了。

对于将其加入后如何算新的贡献，我们可以再枚举左端点以及其对应的右端点，进行分类讨论。设当前的区间为\([l,r]\)，中间点为\(md\)，当前长度为\(len_j=2^j-1\)，\(lcp\)为\(s_{l,\cdots md-1}\)和\(s_{md+1,\cdots r}\)的\(lcp\)。

1. \(g_{l,j-1}=1,g_{md+1,j-1}=1,lcp=len_{j-1}\)，我们只需要考虑第二个限制，枚举\(s_{md}\)可以是哪个字符即可；
2. \(g_{l,j-1}=1,g_{md+1,j-1}=1,_l=len_{j-1}\)，这种情况下\(lcp\)必须等于\(len_{j-2}\)，也就是说，只允许\(s_{l+len_{j-2}}\neq s_{md+1+len_{j-2}}\)，否则这个串就没有贡献。所以此时我们判一下将这两个字符中的一个改为另一个之后这个串是否合法就行了；
3. \(g_{l,j-1}+g_{md+1,j-1}=1\)，此时我们只允许\(s_{l+lcp}\neq s_{md+1+lcp}\)，所以再求一下这两个位置后面的\(lcp\)，判一下，然后看能不能把不为gray串的那边的那个不一样的字符换成是gray串的那边对应的字符即可。
4. 其余情况都无法产生贡献。

我们将上述操作的过程用一个数组\(con_{i,j}\)记录下来即可。剩下的东西就很好做了。

时间复杂度：\(O(nlogn \times 26)\)，当然肯定不会跑满。建议用sa求lcp，可以少一个二分的log。

代码：

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
template<class D>I read(D &res){
    res=0;register D g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
char c[101000];
int n,m,mx,val,ln[30],s[101000][30],g[101000][20],a[101000],sa[101000],tp[101000],buc[101000],tot,rk[101000],hei[101000],f[101000][20],lg[101000];
ll w[101000],ans,sum,con[101000][30];
I build_sa(){
    m=30;
    F(i,1,n)buc[rk[i]=a[i]]++;
    F(i,1,m)buc[i]+=buc[i-1];
    FOR(i,n,1)sa[buc[rk[i]]--]=i;
    for(re k=1;k<=n;k<<=1){
        re tot=0;
        F(i,n-k+1,n)tp[++tot]=i;
        F(i,1,n)if(sa[i]>k)tp[++tot]=sa[i]-k;
        F(i,1,m)buc[i]=0;
        F(i,1,n)buc[rk[i]]++;
        F(i,1,m)buc[i]+=buc[i-1];
        FOR(i,n,1)sa[buc[rk[tp[i]]]--]=tp[i],tp[i]=0;
        swap(rk,tp);
        rk[sa[1]]=tot=1;
        F(i,2,n)rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+k]==tp[sa[i]+k])?tot:++tot;
        if(tot==n)break;
        m=tot;
    }
    re k=0;
    F(i,1,n){
        if(rk[i]==1)continue;
        if(k)k--;
        re p=sa[rk[i]-1];
        while(a[i+k]==a[p+k])k++;
        hei[rk[i]]=k;
    }
    lg[0]=-1;F(i,1,n)f[i][0]=hei[i],lg[i]=lg[i>>1]+1;
    F(j,1,lg[n])F(i,1,n-(1<<j)+1)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
IN ques_lcp(int x,int y){
    if(x==y)return n-x+1;x=rk[x];y=rk[y];if(x>y)swap(x,y);x++;
    re len=lg[y-x+1];return min(f[x][len],f[y-(1<<len)+1][len]);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>c+1;n=strlen(c+1);
    F(i,1,n)a[i]=c[i]-'a'+1;
    build_sa();
    F(i,1,n){
        F(j,1,26)s[i][j]=s[i-1][j];
        s[i][a[i]]++;
    }
    F(i,1,n)g[i][1]=1;w[1]=1;
    re l,r,md,_l,_r,sn;mx=lg[n]+1;ans=n;
    F(i,1,mx)ln[i]=(1<<i)-1;
    F(j,2,mx)F(i,1,n-(1<<j)+2){
        l=i;r=i+(1<<j)-2;md=(l+r)>>1;
        if(!g[i][j-1]||!g[md+1][j-1]||ques_lcp(l,md+1)<ln[j-1]||s[r][a[md]]-s[l-1][a[md]]>1)continue;
        g[i][j]=1;w[l]+=(ll)ln[j]*ln[j];w[r+1]-=(ll)ln[j]*ln[j];ans+=(ll)ln[j]*ln[j];
    }
    F(i,2,n)w[i]+=w[i-1];
    F(i,1,n)F(j,1,26)con[i][j]=1;
    F(j,2,mx)F(i,1,n-(1<<j)+2){
        l=i;r=i+(1<<j)-2;md=(l+r)>>1;_l=ques_lcp(l,md+1);
        if(g[i][j-1]&&g[md+1][j-1]){
            if(_l>=ln[j-1]){
                F(k,1,26)if(s[r][k]==s[l-1][k])con[md][k]+=(ll)ln[j]*ln[j];
                continue;
            }
            if(_l<ln[j-2])continue;
            val=a[l+ln[j-2]];if(a[r-ln[j-2]]==a[md])sn=1;else if(val==a[md])sn=-1;else sn=0;
            if(s[r][a[md]]-s[l-1][a[md]]-sn==1)con[r-ln[j-2]][val]+=(ll)ln[j]*ln[j];
            val=a[r-ln[j-2]];if(a[l+ln[j-2]]==a[md])sn=1;else if(val==a[md])sn=-1;else sn=0;
            if(s[r][a[md]]-s[l-1][a[md]]-sn==1)con[l+ln[j-2]][val]+=(ll)ln[j]*ln[j];
            continue;
        }
        if(!g[i][j-1]&&!g[md+1][j-1])continue;
        if(g[i][j-1]){
            _r=ques_lcp(l+_l+1,md+_l+2);if(_l+_r+1<ln[j-1])continue;
            val=a[l+_l];if(a[md+1+_l]==a[md])sn=1;else if(val==a[md])sn=-1;else sn=0;
            if(s[r][a[md]]-s[l-1][a[md]]-sn==1)con[md+1+_l][val]+=(ll)ln[j]*ln[j];
        }
        if(g[md+1][j-1]){
            _r=ques_lcp(l+_l+1,md+_l+2);if(_l+_r+1<ln[j-1])continue;
            val=a[md+1+_l];if(a[l+_l]==a[md])sn=1;else if(val==a[md])sn=-1;else sn=0;
            if(s[r][a[md]]-s[l-1][a[md]]-sn==1)con[l+_l][val]+=(ll)ln[j]*ln[j];
        }
    }
    sum=0;
    F(i,1,n)F(j,1,26)if(a[i]^j)sum=max(sum,con[i][j]-w[i]);
    ans+=sum;cout<<ans;
    return 0;
}