多重集合 \(S\) に対して、

• 要素の追加
• 要素の削除
• \(S=\lbrace 1,2,\ldots,K\rbrace\) であるかの判定

の操作をそれぞれ高速に行うことができればこの問題を解くことができることが分かります。実際、

• \(S=\lbrace A_1,A_2,\ldots,A_{K-1}\rbrace\) とする
• \(i=K,K+1,\ldots,N\) に対して以下の操作を行う
  • \(S\) に \(A_i\) を追加する
  • \(S=\lbrace 1,2,\ldots,K\rbrace\) であるか判定する。
  • \(S\) から \(A_{i-K+1}\) を削除する
• 上のループで \(S=\lbrace 1,2,\ldots,K\rbrace\) が成り立った回数が求める答えである。

というアルゴリズムで答えを求めることができることが分かります。

そして、上の操作は \(cnt[k]=\lbrace\) \(S\) の中に含まれる要素 \(k\) の個数 \(\rbrace\) と \(cnt[k]=1\) を満たす \(k\) の個数をそれぞれ保持することでどの操作も \(O(1)\) 時間で判定することができます。

詳しい実装は下の実装例を参考にしてください。

実装例 (Python3)

n, k = map(int, input().split())
a = [x - 1 for x in map(int, input().split())]
cnt = [0] * k
for i in range(k - 1):
    cnt[a[i]] += 1
cnt_one = cnt.count(1)

def add(idx, val):
    global cnt_one
    cnt_one -= cnt[idx] == 1
    cnt[idx] += val
    cnt_one += cnt[idx] == 1

ans = 0
for i in range(k - 1, n):
    add(a[i], 1)
    ans += cnt_one == k
    add(a[i - k + 1], -1)
print(ans)