【普及/提高-】环状交替子段计数

题目描述

给定一个长度为 n 的环状序列 colors[0…n-1]（相邻性按环计算，即 colors[n-1] 与 colors[0] 也相邻）。定义一个长度为 k 的环状连续子段为从某个起点 s 开始，依次取 k 个元素：

colors[s], colors[(s+1)%n], … , colors[(s+k-1)%n]

若该子段中任意相邻两项都不相等（即对所有 t，有 colors[(s+t)%n] != colors[(s+t-1)%n]），则称其为交替的。

请你统计：共有多少个起点 s（0 ≤ s < n），使得从 s 开始的长度为 k 的环状连续子段是交替的。

输入格式

• 第一行包含两个整数 n, k。
• 第二行包含 n 个整数，表示序列 colors[0…n-1]。

输出格式

• 输出一个整数，表示满足条件的起点个数。

数据范围

• 1 ≤ n ≤ 2 * 10^5
• 1 ≤ k ≤ n
• 0 ≤ colors[i] ≤ 10^9
• 需要在 O(n) 或 O(n log n) 时间内通过。

说明 / 提示

• 当 k = 1 时，任意单个元素子段都视为交替，因此答案为 n。
• 序列是环状的，起点可在 0…n-1 中任取一个。
• 判断交替仅比较相邻是否相等，与具体数值大小无关。

样例 1

输入

5 3
1 2 1 2 1

输出

5

解释 整个序列本身相邻都不相等，任取起点，长度为 3 的子段均交替，共 5 个。

样例 2

输入

6 2
3 3 1 2 2 1

输出

3

解释 满足相邻不等的长度为 2 的环状子段起点有：s=2(1,2), s=3(2,2)×, s=4(2,1), s=5(1,3)（注意环首尾相邻），再加上 s=0(3,3)×, s=1(3,1)，共 3 个：s=1,2,4。

样例 3

输入

4 4
7 7 7 7

输出

0

解释 任意相邻两项都相等，不可能构成交替子段。