P8631 题解

· · 题解

\textbf{P8631}
  • 定义 f(s) 为字符串 s 的本质不同子串数量，g(s) 是字符串本质不同的长度为奇数的回文串数量，求 \max\limits_{i=1}^{n-1}\{g(s[1\ldots i]) \cdot (f(s[i+1\ldots n])-g(s[i+1\ldots n]))\}

热知识：这道题在昨天还是蓝的。

我们对于 s 的所有前后缀 t，求出所有 f(t),g(t) 然后暴力枚举计算答案，可以发现这道题分为两部分：

这一部分是 P4070 生成魔咒，使用 SA 或 SAM 均可。

注意到字符串本质不同回文子串数量是 \mathcal O(n) 级别的，枚举回文中心 i 并求出回文半径 len，若当前右端点 r=i+len-1 比之前 r 的最大值 r' 还大，那么枚举右端点 r'+1 \sim r，如果这个回文串之前没出现过，则所有 k \le r 的前缀 [1,k] 的回文串数量加一，差分即可。判断有没有出现过可以哈希，但是既然我们已经写 SA 了不妨直接用 SA 判断：对于每个 len 维护一个存 rk 的 set，每次和前驱后继查 \operatorname{LCP}。回文半径也可以用后缀数组求。

那么这道题就做完了，时间复杂度 \mathcal O(n \log n)。

/**
 *    author: sunkuangzheng
 *    created: 29.02.2024 08:40:22
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
struct SA{
    int sa[N],rk[N],ok[N],h[N],st[20][N],n;
    void build(string s){
        n = s.size(); s = " " + s;
        for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = s[i];
        for(int j = 1;j < n;j *= 2){
            for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
            sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[x + j] < rk[y + j];});
            auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[x + j] == ok[y + j];};
            for(int i = 1;i <= n;i ++) if(cmp(sa[i],sa[i-1])) rk[sa[i]] = p; else rk[sa[i]] = ++p; if(p == n) break;
        }for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) 
        for(k --,k = max(k,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
        for(int i = 1;i <= n;i ++) st[0][i] = h[i];
        for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            st[j][i] = min(st[j-1][i],st[j-1][i+(1<<j-1)]);
    }int lcp(int i,int j){
        if(i == j) return n - sa[i] + 1; 
        if(i > j) swap(i,j);
        int k = __lg(j - i);
        return min(st[k][i+1],st[k][j-(1<<k)+1]);
    }
}s1,s2;
int T,n; string s,t; ll f[N],g[N],ans1[N],ans2[N],ans3[N];
void los(){
    cin >> n >> s,t = s,s = s + '#' + string(s.rbegin(),s.rend());
    s1.build(s),s2.build(t);
    auto rev = [&](int i){return n + 2 + n - i;};
    set<int> fk; ll sm = 0; 
    for(int i = n;i >= 1;i --){
        auto it = fk.lower_bound(s2.rk[i]);
        if(it != fk.end()) sm -= s2.h[*it],s2.h[*it] = s2.lcp(*it,s2.rk[i]),sm += s2.h[*it];
        if(it != fk.begin()) s2.h[s2.rk[i]] = s2.lcp(s2.rk[i],*(--it)),sm += s2.h[s2.rk[i]]; 
            else s2.h[s2.rk[i]] = 0;
        fk.insert(s2.rk[i]),ans1[i] = 1ll * (n - i + 1) * (n - i + 2) / 2 - sm;
    }fk.clear(); static set<int> f[N];
    int mxr = 0; 
    for(int i = 1;i <= n;i ++){
        int d = s1.lcp(s1.rk[i],s1.rk[rev(i)]),r = i + d - 1;
        if(r > mxr){
            for(int j = mxr + 1;j <= r;j ++){
                int l = i - (j - i),len = j - l + 1,lcp = 0;
                auto it = f[len].lower_bound(s1.rk[l]);
                if(it != f[len].end()) lcp = max(lcp,s1.lcp(s1.rk[l],*it));
                if(it != f[len].begin()) lcp = max(lcp,s1.lcp(s1.rk[l],*(--it)));
                if(lcp < len) ans2[j] ++,f[len].insert(s1.rk[l]);
            }mxr = r;
        }
    }int mnl = n + 1; 
    for(int i = 1;i <= n;i ++) f[i].clear();
    for(int i = n;i >= 1;i --){
        int d = s1.lcp(s1.rk[i],s1.rk[rev(i)]),l = i - d + 1;
        if(l < mnl){
            for(int j = mnl - 1;j >= l;j --){
                int r = i + (i - j),len = r - j + 1,lcp = 0;
                auto it = f[len].lower_bound(s1.rk[j]);
                if(it != f[len].end()) lcp = max(lcp,s1.lcp(s1.rk[j],*it));
                if(it != f[len].begin()) lcp = max(lcp,s1.lcp(s1.rk[j],*(--it)));
                if(lcp < len) ans3[j] ++,f[len].insert(s1.rk[j]);
            }mnl = l;
        }
    }ll ans = 0;
    for(int i = 1;i <= n;i ++) ans2[i] += ans2[i - 1];
    for(int i = n;i >= 1;i --) ans3[i] += ans3[i + 1];
    for(int i = 1;i < n;i ++) ans = max(ans,1ll * ans2[i] * (ans1[i + 1] - ans3[i + 1]));
    cout << ans;
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}