CF1913F

Sunny郭 · 2023-12-21 08:49:15 · 题解

虽然是 CF，但是赛后补题。hash， 启动！（其实是不会SA）

字符集是 26 的，可以考虑直接枚举改哪个字符，改成什么。

但是我们不可能每次都去枚举，考虑修改一个字符对于答案的改变。

设当前修改位置为 k。

• 本来跨过 k 的回文串都会消失

考虑怎么计算预处理这个事情。

发现当回文串形如 a b c b a 时，改变每个位置的字符后减少的回文串数量形如 1 2 3 2 1 这样先上升再下降的形式。考虑维护这个东西。

设 l 为回文串左端点，r 为回文串右端点，i 为回文串中心。我们不用平时的一阶变化（即直接差分，形如 s_l+1，s_{r+1}-1）。考虑二阶变化，我们维护一个 dt 数组记录变化量，在 dt_l+1，dt_{i+1}-2，dt_{r+1}+1，我们再维护一个数组 c，这个也就是最终记录每个位置有多少字符串跨过去的影响了。

考虑如何维护 c？从左往右扫，记录累加的变化量 dt 并记录在 c 中。

对于形如 a b c c b a 的字符串留给作者思考。

• 本来回文串右端点为 k-1 且回文中心小于 k 的，或者本来回文串左端点为 k+1 且回文中心大于 k 的。

这是好维护的，用 vector 预处理每个地方有哪些回文中心，枚举 k 的时候拿出来算就行。考虑怎么算？直接 hash + 二分！

时间复杂度是 O(n|\Sigma|+ n \log n)

记得开 long long。

//奇回文串：形如aba，偶回文串：形如abba
#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int N = 3e5 + 7;
const int B = 1721, M = 1e9 + 3;
int i, j, k, n, m, l, r, mid, res, sum, L, R, ans, ai;
int hl[N], hr[N], g[N];//hash使用 
int p[N], q[N];//pi表示以i为回文中心的奇回文串的回文半径，q偶回文串 
int c[N], dt[N];
//dt变化量，c回文串个数， 
vector<int> u[N], v[N];
//u_i以i为端点的奇回文串的回文中心，v_i存偶回文串 
char s[N], as;
int subl(int x, int y) {return (hl[y] - hl[x] * g[y - x] % M + M) % M;}
int subr(int x, int y) {return (hr[x] - hr[y] * g[y - x] % M + M) % M;}
void init_hash() {
    for(g[0]=i=1; i<=n; i++) g[i] = g[i-1] * B % M;
    for(i=1; i<=n; i++) hl[i] = (hl[i-1] * B % M + s[i]) % M;
    for(i=n; i>=1; i--) hr[i] = (hr[i+1] * B % M + s[i]) % M;
}
void init_string() {
    for(i=1; i<=n; i++) {
        l = 0, r = min(i, n - i + 1);
        while(l <= r) {
            mid = l + r >> 1;
            if(subl(i - mid, i) == subr(i, i + mid)) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        sum += p[i] = res, l = i - res + 1, r = i + res - 1;
        u[l].pb(i);
        if(l != r) u[r].pb(i);
        ++dt[l], ++dt[r+2], dt[i+1] -= 2;
    }
    for(i=1; i<n; i++) {
        if(s[i] != s[i+1]) continue;
        l = 0, r = min(i, n - i);
        while(l <= r) {
            mid = l + r >> 1;
            if(subl(i - mid, i) == subr(i+1, i + mid + 1)) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        sum += q[i] = res, l = i - res + 1, r = i + res;
        v[l].pb(i);
        if(l != r) v[r].pb(i);
        ++dt[l], ++dt[r+2], --dt[i+1], --dt[i+2];
    }
    int d = 0, s = 0;
    for(i=1; i<=n; i++) d += dt[i], s += d, c[i] = s;
    ans = sum;
}
void solve() {
    for(k=1; k<=n; k++) {
        for(char s='a'; s<='z'; s++) {
            int tmp = sum - c[k] + p[k];
            for(int i : u[k-1]) {
                if(i >= k) continue;
                l = p[i] + 2, r = min(i, n - i + 1);
                L = i - p[i], R = i + p[i] + 1;
                if(::s[L] != s) continue;
                --L; res = l - 1;
                while(l <= r) {
                    mid = l + r >> 1;
                    if(subl(i - mid, L) == subr(R, i + mid)) res = mid, l = mid + 1;
                    else r = mid - 1;
                }
                tmp += res - p[i];
            }
            for(int i : u[k+1]) {
                if(i <= k) continue;
                l = p[i] + 2, r = min(i, n - i + 1);
                L = i - p[i] - 1, R = i + p[i];
                if(::s[R] != s) continue;
                ++R; res = l - 1;
                while(l <= r) {
                    mid = l + r >> 1;
                    if(subl(i - mid, L) == subr(R, i + mid)) res = mid, l = mid + 1;
                    else r = mid - 1;
                }
                tmp += res - p[i];
            }
            for(int i : v[k-1]) {
                if(i >= k-1) continue;//注意这里，要-1，不然会被讨论区大佬hack
                L = i - q[i], R = i + q[i] + 2;
                l = q[i] + 2, r = min(i, n - i);
                if(::s[L] != s) continue;
                --L; res = l - 1;
                while(l <= r) {
                    mid = l + r >> 1;
                    if(subl(i - mid, L) == subr(R, i + mid + 1)) res = mid, l = mid + 1;
                    else r = mid - 1;
                }
                tmp += res - q[i];
            }
            if(::s[k-1] == s) {
                i = k - 1; res = 1;
                l = 2, r = min(i, n - i);
                L = i - 1, R = k + 1;
                while(l <= r) {
                    mid = l + r >> 1;
                    if(subl(i - mid, L) == subr(R, i + mid + 1)) res = mid, l = mid + 1;
                    else r = mid - 1;
                }
                tmp += res;
            }
            for(int i : v[k+1]) {
                if(i <= k) continue;
                L = i - q[i] - 1, R = i + q[i] + 1;
                l = q[i] + 2, r = min(i, n - i);
                if(::s[R] != s) continue;
                ++R; res = l - 1;
                while(l <= r) {
                    mid = l + r >> 1;
                    if(subl(i - mid, L) == subr(R, i + mid + 1)) res = mid, l = mid + 1;
                    else r = mid - 1;
                }
                tmp += res - q[i];
            }
            if(::s[k+1] == s) {
                i = k; res = 1;
                l = 2, r = min(i, n - i);
                L = k - 1, R = k + 2;
                while(l <= r) {
                    mid = l + r >> 1;
                    if(subl(i - mid, L) == subr(R, i + mid + 1)) res = mid, l = mid + 1;
                    else r = mid - 1;
                }
                tmp += res;
            }
            if(tmp == ans) {
                if(ai != k && (::s[ai] < as || (::s[ai] == as && ::s[k] > s))) ai = k, as = s;
            }
            if(tmp > ans) {
                ans = tmp;
                ai = k, as = s;
            }
        }
    }
}
signed main() {
    scanf("%lld%s", &n, s+1);
    init_hash();
    init_string();
    solve();
    s[ai] = as;
    printf("%lld\n%s", ans, s+1);
    return 0;
}