AtCoder ABC 290 E Make it Palindrome

标签: abc

对于数列 ,定义 表示将 变成回文串最少的需要改变的元素数量。给定数组 ,求其所有连续子串的 值之和。

对于每一个 对,若 ,则会产生 的贡献。发现找这个不同值对不方便,可以考虑反面,算出所有数对的贡献再减去相同数对的贡献。

令值 出现的所有位置为 ,任意一个 中两个数组成的数对都会产生数贡献。考虑如何计算所有相同数对的负贡献。枚举 ,令 分别表示当前考虑的 的左右端点。如果 ,则每一个以 开始的相同数对都可以产生 的负贡献,然后把 ,反之亦然。计算所有数对的贡献也可以用类似的方法。

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> pos(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i]--;
        pos[a[i]].emplace_back(i);
    }
    long long res = 0;
    {
        int l = 0, r = n - 1;
        while (l <= r) {
            if (l + 1 < n - r) {
                res += (long long)(r - l + 1) * (l + 1);
                l++;
            } else {
                res += (long long)(r - l + 1) * (n - r);
                r--;
            }
        }
    }
    // cout << res << endl;
    for (int i = 0; i < n; i++) {
        int l = 0, r  = pos[i].size() - 1;
        auto &p = pos[i];
        while (l <= r) {
            if (p[l] + 1 < n - p[r]) {
                res -= (long long)(r - l + 1) * (p[l] + 1);
                l++;
            } else {
                res -= (long long)(r - l + 1) * (n - p[r]);
                r--;
            }
        }
    }
    cout << res << endl;
}