Make it Palindrome

题目描述

对于一个序列 $X$，令 $f(X) =$（将 $X$ 变为回文序列所必须修改的最少元素个数）。 给定长度为 $N$ 的序列 $A$，求对 $A$ 的所有 连续 子数组 的 $f(X)$ 之和。 这里，长度为 $m$ 的序列 $X$ 当且仅当对所有 $1 \le i \le m$，第 $i$ 个元素与第 $(m+1-i)$ 个元素相等时，称为回文序列。

输入格式

输入按下述格式由标准输入给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出一个整数，表示答案。

5
5 2 1 2 2

9

提示

输入中的所有数值均为整数。 $1 \le N \le 2 \times 10^5$ $1 \le A_i \le N$$f(5) = 0$ $f(2) = 0$ $f(1) = 0$ $f(2) = 0$ $f(2) = 0$ $f(5,2) = 1$ $f(2,1) = 1$ $f(1,2) = 1$ $f(2,2) = 0$ $f(5,2,1) = 1$ $f(2,1,2) = 0$ $f(1,2,2) = 1$ $f(5,2,1,2) = 2$ $f(2,1,2,2) = 1$ $f(5,2,1,2,2) = 1$

因此，所求答案为 $9$.

标签: AtCoder|abc290E

来源

AtCoder|abc290E