102904: [Atcoder]ABC290 E - Make it Palindrome
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：2
Solved：0
Description
Score : $500$ points
Problem Statement
For a sequence $X$, let $f(X) =$ (the minimum number of elements one must modify to make $X$ a palindrome).
Given a sequence $A$ of length $N$, find the sum of $F(X)$ over all contiguous subarrays of $A$.
Here, a sequence $X$ of length $m$ is said to be a palindrome if and only if the $i$-th and the $(m+1-i)$-th elements of $X$ are equal for all $1 \le i \le m$.
Constraints
- All values in the input are integers.
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i \le N$
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the answer as an integer.
Sample Input 1
5 5 2 1 2 2
Sample Output 1
9
- $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$
Therefore, the sought answer is $9$.
Input
题意翻译
对于一个序列 $X$，我们设函数 $f(X)$ 表示将 $X$ 修改为回文串需要修改的数的数量。 现在，给定一个长度为 $N$ 的序列 $A$，问 $A$ 的所有连续的子序列（也就是子串）的 $f(X)$ 的值的和Output
分数：500分
问题描述
对于一个序列$X$，令$f(X)=$（将$X$变为回文串所需的最少元素修改次数）。
给定一个长度为$N$的序列$A$，求$A$的所有连续子数组的$f(X)$之和。
在这里，长度为$m$的序列$X$被称为回文串，当且仅当$X$的第$i$个元素和第$(m+1-i)$个元素对于所有$1 \le i \le m$都相等。
约束
- 输入中的所有值都是整数。
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i \le N$
输入
输入通过标准输入给出以下格式：
$N$ $A_1$ $A_2$ $\dots$ $A_N$
输出
将答案输出为整数。
样例输入 1
5 5 2 1 2 2
样例输出 1
9
- $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$。