AT_abc290_e [ABC290E] Make it Palindrome

题目描述

对于一个数列 $X$，定义 $f(X)$ 为：将 $X$ 变为回文数列所需修改的元素个数的最小值。

给定一个长度为 $N$ 的数列 $A$，请计算所有 $A$ 的连续子序列 $X$ 的 $f(X)$ 之和。

这里，长度为 $m$ 的数列 $X$ 是回文数列，当且仅当对于所有满足 $1 \le i \le m$ 的整数 $i$，$X$ 的第 $i$ 项与第 $m+1-i$ 项相等。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

5
5 2 1 2 2

输出 #1

9

说明/提示

限制条件

• 输入均为整数。
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$

样例解释 1

• $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$。

由 ChatGPT 4.1 翻译