CF190D Non-Secret Cypher

伯兰德开始在与弗拉特兰的战争中掌握主动权。为了将敌人驱逐出自己的故土，伯兰德人需要准确知道敌军的后备力量中还剩下多少名弗拉特兰士兵。幸运的是，侦察队在清晨俘虏了一名敌人，他随身携带着一条被加密的秘密信息，这正是伯兰德人急需的信息。 被俘虏的敌人手中有一个正整数数组。伯兰德情报部门早已知晓弗拉特兰的密码：为了传递一条包含数字 $m$ 的信息，敌人会使用一个整数数组 $a$。该数组的子数组中，包含至少 $k$ 个相同数字的子数组个数恰好为 $m$。数值 $k$ 伯兰德军队早已知晓，因此图里斯托夫将军再次让下士 VASYA 完成一个简单任务：破译弗拉特兰人的信息。 请你帮助 VASYA，给定整数数组 $a$ 和数字 $k$，找出数组 $a$ 的所有子数组中，包含至少 $k$ 个相同整数的子数组数量。 子数组 $a[i... j]$ $(1\leq i\leq j\leq n)$ 是数组 $a=(a_1, a_2, ..., a_n)$ 的一段连续元素，从第 $i$ 个到第 $j$ 个元素：$a[i... j]=(a_i, a_{i+1}, ..., a_j)$。

第一行包含两个用空格分隔的整数 $n$、$k$，$(1\leq k\leq n\leq 4\cdot 10^{5})$，表示数组的长度和每个子数组内要求最少相同数字的个数。 第二行包含 $n$ 个用空格分隔的整数 $a_i$，$(1\leq a_i \leq 10^9)$，表示数组的元素。

输出一个整数，表示数组 $a$ 的所有子数组中，包含至少 $k$ 个相同整数的子数组数量。 请勿在 C++ 中使用 %lld 读写 64 位整数。建议使用 cin、cout 流或 %I64d。

在第一个样例中，有三个子数组包含至少两个相同数字：(1,2,1)、(2,1,2) 和 (1,2,1,2)。 在第二个样例中，有两个子数组包含三个相同数字：(1,2,1,1,3) 和 (1,2,1,1)。 在第三个样例中，任意一个子数组都有至少一个 1。总共有 6 个子数组：(1)、(1)、(1)、(1,1)、(1,1) 和 (1,1,1)。 由 ChatGPT 5 翻译