Preparando MOJI
Petya and his friend, the robot Petya++, have a common friend — the cyborg Petr#. Sometimes Petr# comes to the friends for a cup of tea and tells them interesting problems.
Today, Petr# told them the following problem.
A palindrome is a sequence that reads the same from left to right as from right to left. For example, $$$[38, 12, 8, 12, 38]$$$, $$$[1]$$$, and $$$[3, 8, 8, 3]$$$ are palindromes.
Let's call the palindromicity of a sequence $$$a_1, a_2, \dots, a_n$$$ the minimum count of elements that need to be replaced to make this sequence a palindrome. For example, the palindromicity of the sequence $$$[38, 12, 8, 38, 38]$$$ is $$$1$$$ since it is sufficient to replace the number $$$38$$$ at the fourth position with the number $$$12$$$. And the palindromicity of the sequence $$$[3, 3, 5, 5, 5]$$$ is two since you can replace the first two threes with fives, and the resulting sequence $$$[5, 5, 5, 5, 5]$$$ is a palindrome.
Given a sequence $$$a$$$ of length $$$n$$$, and an odd integer $$$k$$$, you need to find the sum of palindromicity of all subarrays of length $$$k$$$, i. e., the sum of the palindromicity values for the sequences $$$a_i, a_{i+1}, \dots, a_{i+k-1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n-k+1$$$.
The students quickly solved the problem. Can you do it too?
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$, $$$k$$$ is odd) — the length of the sequence and the length of subarrays for which it is necessary to determine whether they are palindromes.
The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the sequence itself.
Output a single integer — the total palindromicity of all subarrays of length $$$k$$$.
8 5 1 2 8 2 5 2 8 6
4
9 9 1 2 3 4 5 4 3 2 1
0
In the first example, the palindromicity of the subarray $$$[1, 2, 8, 2, 5]$$$ is $$$1$$$, the palindromicity of the string $$$[2, 8, 2, 5, 2]$$$ is also $$$1$$$, the palindromicity of the string $$$[8, 2, 5, 2, 8]$$$ is $$$0$$$, and the palindromicity of the string $$$[2, 5, 2, 8, 6]$$$ is $$$2$$$. The total palindromicity is $$$1+1+0+2 = 4$$$.
In the second example, the only substring of length $$$9$$$ coincides with the entire string, and its palindromicity is $$$0$$$, so the answer is also $$$0$$$.
Informação
Provedor Codeforces
Código CF1808D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:38:05
Relacionados