题目：AT_abc290_d

链接：洛谷，AT，逐月

题意

• \(f(x)\) 为序列 \(x\) 最少需要改变的字符数量使得 \(x\) 为回文串。给定长度为 \(n\) 的序列 \(a\)，求所有子段的 \(f(x)\) 之和。

• 数据范围：$ 1 \le a_i \le n \le 10^5$。

思路

\(n^2\) 暴力

我们可以对于每一对数 \((a_i, a_j)(1 \le i < j \le n)\) 求它对答案的贡献，若 \(a_i \ne a_j\)，贡献为 \(\min(i, n - j + 1)\)，否则贡献为 \(0\)。

正解1

• 上述做法显然这样是过不了此题的，我们不能枚举每一对数。我们发现如果 \(a_i = a_j\) 才有贡献会好做许多。

• 对于我们每个数值 \(x\)，用 vector 记录所有 \(a_i = i\) 的 \(i\)，然后可以枚举每个数值 \(x\)，在枚举元素 \(p_{x, i}\)，那么 \((p_{x, i}, p_{x, j})(i < j)\) 的贡献为 \(\min(p_{x, i}, n - p_{x, j} + 1)\)。那么会有一个分界线，一边是 \(p_{x, i} \le n - p_{x, j} + 1\)，另一边则是 \(p_{x, i} > n - p_{x, j} + 1\)。左边所有贡献全是 \(p_{x, i}\)，右边则是 \(n - p_{x, j} + 1\)。

• 所以只需要二分或双指针这个分界线，左边全部贡献用个数 $ \times p_{x, i}$，右边用一个后缀和即可，再用所有的对数减去相等的即是答案。

正解2

• 上面是用全部减去相同的，相当于是容斥，但是也可以直接做。我们每次将关于当前区间 \([l, r]\) 的 \(l, r\) 再 \([l, r]\) 的贡献全算完，然后就可以删掉这两个数了，因为后面的计算已经和它们没有关系了。

• 但是怎么计算贡献呢？令 \(cnt_i\) 表示 \(i\) 出现的次数。那么 \(l, r\) 的贡献为 \((cnt_{a_l} - 1) \times l + (cnt_{a_r} - 1) \times l - (a_l \ne a_r) \times l\)。为什么乘 \(l\) 呢，因为 \([l, r]\) 内的数要与 \(l, r\) 组成一对那么贡献就是 \(l\) 或 \(n - r + 1\)。

时间复杂度

双指针：\(O(n)\)。