CF1808D Petya, Petya, Petr, and Palindromes

Petya 和他的朋友机器人 Petya++ 有一个共同的朋友——半机械人 Petr#。有时 Petr# 会来找他们喝茶，并给他们讲一些有趣的问题。 今天，Petr# 给他们出了如下问题。 回文是指从左到右和从右到左读都相同的序列。例如，$[38, 12, 8, 12, 38]$、$[1]$ 和 $[3, 8, 8, 3]$ 都是回文。 我们定义一个序列 $a_1, a_2, \dots, a_n$ 的“回文性”为：将该序列变为回文所需最少替换元素的次数。例如，序列 $[38, 12, 8, 38, 38]$ 的回文性为 $1$，因为只需将第 $4$ 个位置的 $38$ 替换为 $12$ 即可。而序列 $[3, 3, 5, 5, 5]$ 的回文性为 $2$，可以将前两个 $3$ 替换为 $5$，得到 $[5, 5, 5, 5, 5]$，这是一个回文。 给定一个长度为 $n$ 的序列 $a$，以及一个奇数 $k$，你需要计算所有长度为 $k$ 的子数组的回文性之和。也就是说，对于所有 $i$ 从 $1$ 到 $n-k+1$，计算 $a_i, a_{i+1}, \dots, a_{i+k-1}$ 的回文性，并将这些值求和。 学生们很快就解决了这个问题。你能做到吗？

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le n$，$k$ 为奇数）——序列的长度和需要判断回文的子数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \cdot 10^5$）——给定的序列。

输出一个整数，表示所有长度为 $k$ 的子数组的回文性之和。

在第一个样例中，子数组 $[1, 2, 8, 2, 5]$ 的回文性为 $1$，子数组 $[2, 8, 2, 5, 2]$ 的回文性也为 $1$，子数组 $[8, 2, 5, 2, 8]$ 的回文性为 $0$，子数组 $[2, 5, 2, 8, 6]$ 的回文性为 $2$。总回文性为 $1+1+0+2=4$。 在第二个样例中，唯一的长度为 $9$ 的子数组就是整个序列，其回文性为 $0$，所以答案也是 $0$。 由 ChatGPT 4.1 翻译