← 返回题目列表

Codeforces · 2146/E

E. 又一个 MEX 问题

中文机器翻译题面 查看原题

我们定义 重量 ,由 $$$m$$$ 非负整数组成,索引数量 $$$i$$$ ($$$1\le i\le m$$$) 满足 $$$b_i \gt \operatorname{mex}(b)$$$。这里,$$$\operatorname{mex}(b)$$$表示$$$b$$$中整数的最小排除(MEX)$$$^{\text{*}}$$$。

给定一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$。对于它的子数组$$$^{\text{†}}$$$ $$$[a_l, a_{l+1}, \ldots, a_r]$$$,我们表示 子数组的 重量 为 $$$w(l,r)$$$。

对于每 $$$1\le i\le n$$$,你必须找到最大值 重量 覆盖 $$$a$$$ 以索引 $$$i$$$ 结尾的所有子数组。换句话说,你必须为每个 $$$1\le i\le n$$$ 找到 $$$\max\limits_{1\le l\le i} w(l, i)$$$。

$$$^{\text{*}}$$$整数集合 $$$b_1, b_2, \ldots, b_m$$$ 的最小排除 (MEX) 被定义为集合 $$$b$$$ 中不出现的最小非负整数 $$$x$$$。

$$$^{\text{†}}$$$数组 $$$c$$$ 是数组 $$$a$$$ 的子数组,如果 $$$c$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n \le 3\cdot 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le n$$$) — $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数,第 $$$i$$$ 个整数表示最大值 重量 覆盖以索引 $$$i$$$ 结束的 $$$a$$$ 的所有子数组,即 $$$\max\limits_{1\le l\le i}w(l,i)$$$。

示例

输入
复制

6
1
0
5
2 0 3 0 1
6
0 1 2 3 5 4
7
0 2 2 0 4 1 3
8
2 1 0 3 0 2 1 3
15
0 1 9 1 0 2 5 3 7 0 4 15 2 0 1

输出
复制

0
1 1 2 2 1
0 1 2 3 4 5
0 1 2 2 3 2 3
1 2 0 1 1 2 2 3
0 1 2 3 1 1 2 3 4 4 5 6 7 7 3

注意

在第一个测试用例中,我们有 $$$w(1, 1) = 0$$$,因为 $$$\operatorname{mex}([a_1]) = 1$$$,并且没有满足 $$$a_i \gt 1$$$ 的索引。

在第二个测试用例中,我们可以计算 每个子数组 $$$[l,r]$$$ 的 重量 的定义如下:

  1. $$$w(1,1)=1$$$。因此,$$$\max\limits_{1\le l\le 1}w(l,1) =1$$$;
  2. $$$w(1,2)=1$$$ 和 $$$w(2,2)=0$$$。因此,$$$\max\limits_{1\le l\le 2}w(l,2) =1$$$;
  3. $$$w(1,3)=2$$$ 和 $$$w(2,3)=w(3,3)=1$$$。因此,$$$\max\limits_{1\le l\le 3}w(l,3) =2$$$;
  4. $$$w(1,4)=2$$$、$$$w(2,4)=w(3,4)=1$$$ 和 $$$w(4,4)=0$$$。因此,$$$\max\limits_{1\le l\le 4}w(l,4) =2$$$;
  5. $$$w(1,5)=0$$$、$$$w(2,5)=w(3,5)=1$$$ 和 $$$w(4,5)=0,w(5,5)=1$$$。因此,$$$\max\limits_{1\le l\le 5}w(l,5) =1$$$。

例如,$$$w(1, 4) = 2$$$,因为$$$\operatorname{mex}([a_1, a_2, a_3, a_4]) = 1$$$,并且子数组中有两个满足$$$a_i \gt 1$$$的索引:$$$1$$$和$$$3$$$。