問題一覧 > 通常問題

No.2930 Larger Mex

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 99
作問者 : nouka28 / テスター : kusirakusira 👑 loop0919 hirayuu_yc mymelochan uruzunyaa tnodino
お気に入りにしたユーザー ProblemId : 11352 / 自分の提出
問題文最終更新日: 2024-10-12 07:32:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第3回緑以下コンテスト (順位表) の他の問題:

Problem Statement

You are given a sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$ of length $N$ and a non-negative integer $M$. Solve the following problem for each of $k=1,\dots,N$.

Find the number of contiguous subarrays of $A$ of length $k$ whose $\mathrm{mex}$ is at least $M$.

More precisely, find the number of pairs of positive integers $(l,r)$ that satisfy all of the following.

  • $1\leq l\leq r\leq N$
  • $r-l+1=k$
  • $\mathrm{mex}(A_l,A_{l+1},\dots,A_r)\geq M$
What is $\mathrm{mex}$?

The $\mathrm{mex}$ of a set or sequence is the smallest non-negative integer not contained in it.

For example, $\mathrm{mex}(\{0,1,1,2,4\})=3,\mathrm{mex}(\{1,2,3\})=0$.

Constraints

  • $1\leq N\leq 2\times 10^5$
  • $0\leq M\leq 2\times 10^5$
  • $0\leq A_i\leq 2\times 10^5$
  • All inputs are integers.

Input

The input is given from standard input in the following format. 

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print $N$ lines. The $i$-th line should contain the answer for $k=i$.

Sample

Sample 1
Input
5 1
0 3 1 0 2
Output
2
3
3
2
1
  • When $k=1$, the contiguous subarrays of $A$ of length $k$ are $(0),(3),(1),(0),(2)$, and their respective $\mathrm{mex}$ values are $1,0,0,1,0$, so $2$ of them are at least $M$.
  • When $k=2$, the contiguous subarrays of $A$ of length $k$ are $(0,3),(3,1),(1,0),(0,2)$, and their respective $\mathrm{mex}$ values are $1,0,2,1$, so $3$ of them are at least $M$.
  • When $k=3$, the contiguous subarrays of $A$ of length $k$ are $(0,3,1),(3,1,0),(1,0,2)$, and their respective $\mathrm{mex}$ values are $2,2,3$, so $3$ of them are at least $M$.
  • When $k=4$, the contiguous subarrays of $A$ of length $k$ are $(0,3,1,0),(3,1,0,2)$, and their respective $\mathrm{mex}$ values are $2,4$, so $2$ of them are at least $M$.
  • When $k=5$, the contiguous subarray of $A$ of length $k$ is $(0,3,1,0,2)$, and its $\mathrm{mex}$ is $4$, so $1$ of them is at least $M$.
Sample 2
Input
4 0
1 2 3 4
Output
4
3
2
1
Sample 3
Input
20 3
0 2 1 1 1 5 7 0 2 1 4 1 4 8 0 3 0 0 4 2
Output
0
0
2
3
5
6
9
9
10
10
10
9
8
7
6
5
4
3
2
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。