CF1808D.Petya, Petya, Petr, and Palindromes
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 a1,a2,…,an 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 ai,ai+1,…,ai+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≤n≤2⋅105 , 1≤k≤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 a1,a2,…,an ( 1≤ai≤2⋅105 ) — the sequence itself.
输出格式
Output a single integer — the total palindromicity of all subarrays of length k .
输入输出样例
输入#1
8 5 1 2 8 2 5 2 8 6
输出#1
4
输入#2
9 9 1 2 3 4 5 4 3 2 1
输出#2
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 .