Petya, Petya, Petr, and Palindromes
Contest: Codeforces Round 861 (Div. 2)
Difficulty rating: 2100
Tags: binary search, brute force, data structures, two pointers

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?

Input format:
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 format:
Output a single integer — the total palindromicity of all subarrays of length $$$k$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
8 5
1 2 8 2 5 2 8 6

Example output:
4

Example input:
9 9
1 2 3 4 5 4 3 2 1

Example output:
0

Editorial:
Let us see when $$$1$$$ is added to the palindrome. Let there be some string $$$s$$$ of odd length $$$k$$$, consider the index $$$i$$$ to the left of the central one. If this character and the corresponding one on the right side of the string are different, we can replace one of the characters with the other and get $$$+1$$$ to the answer.
Now the problem is as follows: count the number of indices on all substring of length $$$k$$$ such that they differ from the corresponding character in that substring. Let's solve the inverse problem: count the number of indices for all substring of length $$$k$$$ such that the given symbol and its corresponding one are equal. Then simply subtract from the maximum possible number of differences the required number of matches.
Try some symbol $$$c$$$ and count for it the number of matches in all substring. Create a new array $$$a$$$ of length $$$n$$$, that $$$a_i=1$$$ when $$$s_i=c$$$, otherwise $$$a_i=0$$$. Now we have to count the number of indices $$$i$$$ and $$$j$$$ such that $$$i<j$$$, $$$a_i \cdot a_j=1$$$, $$$j-i < k$$$ and $$$(j-i)$$$ mod $$$2=0$$$ (i.e. the distance between indices is even). Let's fix some $$$j$$$ where $$$a_j=1$$$, then indexes $$$j-2$$$, $$$j-4$$$, etc. fit the parity condition. Then we can calculate prefix sums for each parity of indices. That is, $$$pf_{i,par}$$$ means the sum on prefix length $$$i$$$ over all indices with parity equal to $$$par$$$. Then $$$pf_{j-2,par}$$$, where $$$par=j$$$ $$$mod$$$ $$$2$$$ is subtracted from the answer for some fixed $$$j$$$. Total we get the solution for $$$O(n\cdot maxA)$$$, where $$$maxA$$$ is the number of different characters of the string.
To solve the problem faster, we will use the work from the previous solution. Write out separately for each character all its occurrences in the string. Let's go through the symbol and write out all positions with even and odd indices. Solve the problem for even ones (odd ones are solved similarly). We will maintain a sliding window, where the difference between right and left elements is no more than $$$k$$$. When we finish iterating after removing the left element, we will subtract the window length $$$-1$$$ from the answer, because for the left element of the window exactly as many elements have the same parity on the right at a distance of no more than $$$k$$$.
P.S. The solution for $$$O(n\cdot maxA)$$$ can also be reworked into $$$O(n \sqrt{n})$$$ using the trick with «heavy» and «light» numbers.