← 返回题目列表

Codeforces · 1808/D

D. Petya、Petya、Petr 和回文

中文机器翻译题面 查看原题

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$$$,因为用数字 $$$12$$$ 替换第四个位置的数字 $$$38$$$ 就足够了。序列 $$$[3, 3, 5, 5, 5]$$$ 的回文性是 2,因为您可以用 5 替换前两个 3,并且生成的序列 $$$[5, 5, 5, 5, 5]$$$ 是回文。

给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和一个奇数 $$$k$$$,您需要找到长度为 $$$k$$$ 的所有子数组的回文性之和,i。 即,从 $$$1$$$ 到 $$$n-k+1$$$ 的所有 $$$i$$$ 的序列 $$$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

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

注意

在第一个示例中,子数组 $$$[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$$$。