题目描述

难度分:$1485$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

定义$f(b)$表示把数组$b$修改成回文数组，至少要修改多少个数。

例如$f([1,2])=1$，$f([1,2,1])=0$，$f([1,2,3,4])=2$。

输出$a$的所有连续子数组$b$的$f(b)$之和

输入样例$1$

5
5 2 1 2 2

输出样例$1$

9

算法

数学+双指针

如果一个数对($nums[l]$,$nums[r]$)是不相同的，那它们中心对称的子数组有$min(l,n-r+1)$个，也是这个数对所造成的影响（对答案的贡献）。

解释：

1 2 3 4 5 6

如上述数组$3$和$5$是不同的，它们两个中心对称的最大子数组就是

1 (2 3 4 5 6)

最小子数组是

1 2 (3 4 5) 6

理论上我们找到所有这样的数对就可以求出答案，但是找到这些数对需要双重循环遍历，时间复杂度是$O(n^2)$的，会超时。

因此可以求出补集，用总数对的贡献减去好数对的贡献，就能得到坏数对的贡献。假设$nums[l]$包括自己，左边一共有$x=l$个元素，$nums[r]$包括自己，右边一共有$y=n-r+1$个元素。

1. 在$x \lt y$的情况下，此时$r$往左移动到$l+1$都能满足$x \lt y$（一共有$r-l$个位置满足条件），这也就意味着$l$产生的贡献为$x \times (r-l)$。
2. 在$x \geq y$的情况下，此时$l$往右移动到$r-1$也都能满足$x \geq y$，这也意味着$r$产生的贡献为$y \times (r-l)$。

接下来用一个哈希表存储每个数值的位置，遍历每个数值的位置数组，用上述同样的双指针算法计算好数对的贡献即可。

复杂度分析

时间复杂度

计算总数对数量时，对整个数组使用一次相对双指针算法，时间复杂度为$O(n)$；在计算好数对数量时，遍历数组中的所有相同数字，每种数字都是用一次相对双指针算法，总体的时间复杂度也是$O(n)$，因此算法的时间复杂度就是$O(n)$。

空间复杂度

开辟了一个哈希表存储每种数值的索引位置，每个数字都有一个位置，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long LL;
const int N = 200010;
int a[N], n;

int main() {
    scanf("%d", &n);
    unordered_map<int, vector<int>> mp;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mp[a[i]].push_back(i);
    }
    // 总对数
    LL res = 0;
    int l = 1, r = n;
    while(l < r) {
        LL x = l, y = n - r + 1;
        if(x < y) {
            res += x*(r - l);
            l++;
        }else {
            res += y*(r - l);
            r--;
        }
    }
    // 减去好对数
    for(auto&[k, v]: mp) {
        LL left = 0, right = v.size() - 1;
        while(left < right) {
            int l = v[left], r = v[right];
            int x = l, y = n - r + 1;
            if(x < y) {
                res -= x*(right - left);
                left++;
            }else {
                res -= y*(right - left);
                right--;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}