题解 | H. 回文王国

H. 回文王国

经典的计数题目，题目问的是

可以转换为

我们可先算出不修改字符下的答案，枚举比较 的右端点

然后计算 的总比较次数，以及多少次是 的，作差就能计算出 的贡献

对于修改字符的方案，记 表示第 个位置修改为 的变化量，也可以用类似的思路算出来

然后再枚举修改方案即可，细节看代码，有详细注释

事实上本题还存在不挂 的更精细写法，笔者这里的代码并不是最优实现

主要是一下子就想出来了，直接力大砖飞懒得优化了

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define fType ll
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    ll n;
    string s;
    cin >> n >> s;

    ll ans = 0;
    array<vector<ll>, 26> p{};
    array<vector<ll>, 26> ps{};

    // Ori Ans
    foreach (i, 1, n)
    {
        auto id = s[i - 1] - 'a'; // [0,25]

        // 分类讨论计算 ∑min(j,x), 即 i 作为比较的右端点时, 被比较多少次
        // x 其实就是往右扩展的长度, j 是往左扩展长度, j \in[1,y]

        ll x = n - i + 1, y = i - 1;
        if (y > x) // 1..x x x x
        {
            ans += x * (x + 1) / 2;
            ans += (y - x) * x;

            auto it = upper_bound(p[id].begin(), p[id].end(), x);
            ll cnt = distance(p[id].begin(), it);
            if (cnt) ans -= ps[id][cnt - 1];

            cnt = distance(it, p[id].end());
            ans -= cnt * x;
        }
        else // 1...y
        {
            ans += y * (y + 1) / 2;
            if (!ps[id].empty()) ans -= ps[id].back();
        }

        // 存储下出现位置
        p[id].emplace_back(i);

        // 计算下出现位置的前缀和
        if (ps[id].empty())
            ps[id].emplace_back(i);
        else
            ps[id].emplace_back(ps[id].back() + i);
    }

    // dp[ch][i]: 将 s[i-1] 换为 ch 时, 差量增加多少
    array<vector<ll>, 26> dp{};
    foreach (id, 0, 25)
        dp[id].assign(n + 1, 0);

    // Init -> 正向初始化
    foreach (id, 0, 25)
        p[id].clear(), ps[id].clear();

    foreach (i, 1, n)
    {
        // 计算 delta
        foreach (id, 0, 25)
        {
            ll x = n - i + 1, y = i - 1, delta = 0;
            if (y > x) // 1..x x x x
            {
                auto it = upper_bound(p[id].begin(), p[id].end(), x);
                ll cnt = distance(p[id].begin(), it);
                if (cnt) delta += ps[id][cnt - 1];

                cnt = distance(it, p[id].end());
                delta += cnt * x;
            }
            else // 1...y
            {
                if (!ps[id].empty()) delta += ps[id].back();
            }

            dp[id][i] += delta;
        }

        //

        auto id = s[i - 1] - 'a';
        p[id].emplace_back(i);
        if (ps[id].empty())
            ps[id].emplace_back(i);
        else
            ps[id].emplace_back(ps[id].back() + i);
    }

    reverse(s.begin(), s.end());
    // Init <- 反向初始化
    foreach (id, 0, 25)
        p[id].clear(), ps[id].clear();

    foreach (i, 1, n)
    {
        // 计算 delta
        foreach (id, 0, 25)
        {
            ll x = n - i + 1, y = i - 1, delta = 0;
            if (y > x) // 1..x x x x
            {
                auto it = upper_bound(p[id].begin(), p[id].end(), x);
                ll cnt = distance(p[id].begin(), it);
                if (cnt) delta += ps[id][cnt - 1];

                cnt = distance(it, p[id].end());
                delta += cnt * x;
            }
            else // 1...y
            {
                if (!ps[id].empty()) delta += ps[id].back();
            }

            // 因为反转了, 这里索引也要改!
            dp[id][n - i + 1] += delta;
        }

        //

        auto id = s[i - 1] - 'a';
        p[id].emplace_back(i);
        if (ps[id].empty())
            ps[id].emplace_back(i);
        else
            ps[id].emplace_back(ps[id].back() + i);
    }

    reverse(s.begin(), s.end()); // 变回来

    // 枚举修改方案
    ll sub = 0;
    foreach (id, 0, 25)
        foreach (i, 1, n)
            sub = max(sub, dp[id][i] - dp[s[i - 1] - 'a'][i]);

    cout << ans - sub << "\n";
    return 0;
}

扩展思考：如果求的不是差值和，而是差值积呢？