問題一覧 > 通常問題

No.2930 Larger Mex

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 96
作問者 : nouka28 / テスター : kusirakusira 👑 loop0919 hirayuu_yc mymelochan Nyaa Uruzu tnodino
3 ProblemId : 11352 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-12 07:32:51

問題文

長さ NN の非負整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N) と非負整数 MM が与えられます。 k=1,…,Nk=1,\dots,N について以下の問題を解いてください。

AA の長さ kk の連続部分列であって、 その mex\mathrm{mex} が MM 以上であるものは何通りあるか答えてください。

より厳密には正整数の組 (l,r)(l,r) であって、以下を満たすものは何組あるか答えてください。

  • 1≤l≤r≤N1\leq l\leq r\leq N
  • r−l+1=kr-l+1=k
  • mex(Al,Al+1,…,Ar)≥M\mathrm{mex}(A_l,A_{l+1},\dots,A_r)\geq M
mex\mathrm{mex} とは

mex\mathrm{mex} とはその集合あるいは数列に含まれない最小の非負整数のことです。

例えば mex({0,1,1,2,4})=3,mex({1,2,3})=0\mathrm{mex}(\{0,1,1,2,4\})=3,\mathrm{mex}(\{1,2,3\})=0 です。

制約

  • 1≤N≤2×1051\leq N\leq 2\times 10^5
  • 0≤M≤2×1050\leq M\leq 2\times 10^5
  • 0≤Ai≤2×1050\leq A_i\leq 2\times 10^5
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。 

NN MM
A1A_1 A2A_2 …\dots ANA_N

出力

NN 行出力せよ。 ii 行目には k=ik=i としたときの答えを出力せよ。

サンプル

サンプル1
入力
5 1
0 3 1 0 2
出力
2
3
3
2
1
  • k=1k=1 のとき、AA の長さ kk の連続部分列として、(0),(3),(1),(0),(2)(0),(3),(1),(0),(2) があり、それぞれの mex\mathrm{mex} は 1,0,0,1,01,0,0,1,0 なので MM 以上であるものは 22 つあります。
  • k=2k=2 のとき、AA の長さ kk の連続部分列として、(0,3),(3,1),(1,0),(0,2)(0,3),(3,1),(1,0),(0,2) があり、それぞれの mex\mathrm{mex} は 1,0,2,11,0,2,1 なので MM 以上であるものは 33 つあります。
  • k=3k=3 のとき、AA の長さ kk の連続部分列として、(0,3,1),(3,1,0),(1,0,2)(0,3,1),(3,1,0),(1,0,2) があり、それぞれの mex\mathrm{mex} は 2,2,32,2,3 なので MM 以上であるものは 33 つあります。
  • k=4k=4 のとき、AA の長さ kk の連続部分列として、(0,3,1,0),(3,1,0,2)(0,3,1,0),(3,1,0,2) があり、それぞれの mex\mathrm{mex} は 2,42,4 なので MM 以上であるものは 22 つあります。
  • k=5k=5 のとき、AA の長さ kk の連続部分列として、(0,3,1,0,2)(0,3,1,0,2) があり、それぞれの mex\mathrm{mex} は 44 なので MM 以上であるものは 11 つあります。
サンプル2
入力
4 0
1 2 3 4
出力
4
3
2
1
サンプル3
入力
20 3
0 2 1 1 1 5 7 0 2 1 4 1 4 8 0 3 0 0 4 2
出力
0
0
2
3
5
6
9
9
10
10
10
9
8
7
6
5
4
3
2
1

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