OI中“诈骗题”简述

~~诈骗犯，带走！~~

写在前面

由于是诈骗题，建议先思考一遍题目。

对于一个序列 $a_{[l,r]}$ ，定义它的 Mex 变换 $b_{[l,r]}$ 如下：

对于每一个 $l \leq i \leq r$ ，有 $b_i=\text{mex}(\{a_l,a_{l+1},⋯ ,a_{i−1},a_{i+1},⋯ ,a_{r−1},a_r\})$ 。

给定一个长度为 $n$ 的序列 $a_{[1,n]}$ ，你每次操作可以选择一个区间，并将这个区间替换为它的 Mex 变换。

你最多可以进行 $k$ 次操作，你需要最小化操作完成后序列的字典序。构造任意方案。注意：你并不需要最小化你的操作次数。

第一行两个整数 $n,k$ 。

接下来一行 $n$ 个整数，表示序列 $a_{[1,n]}$ 。

第一行输出一个整数 $m$ 表示你使用的操作次数。

接下来 $m$ 行，每行输出两个整数，表示你依次操作的每一个区间。

输入1

1 2	4 3 0 1 2 3

输出1

输入2

1 2	6 1 0 1 2 0 3 4

输出2

1
2

1
2 3

$1 \leq n,k \leq 10^5$ ， $0 \leq a_i \leq n$ 。

解答

先思考： $\text{mex}$ 运算有什么性质？

$A \subset [1,+\infty) \cap \mathbb{Z},\text{mex}(A)=0$ 。人话：如果一个集合中所有数都 $>0$ ，则这个集合的 $\text{mex}$ 值一定为 $0$ 。
$0 \in A,\text{mex}(A) \geq 1$ 。人话：如果一个集合中有 $0$ ，则这个集合的 $\text{mex}$ 值一定 $\geq 1$ 。

此题仅仅用到以上两个性质。

记 $a_{[1,n]}$ 中 $0$ 的数量为 $x$ 。

当 $k=1$ 时，也就是最多只能做一次操作。
1. 当 $x=0$ 时，答案为 $1$ 。对 $a_{[1,n]}$ 做一次变换即可。
2. 当 $x=n$ 时，答案为 $0$ 。本来数列就全零，不需要操作。
3. 其他情况下，答案为 $1$ 。记 $a_{[1,n]}$ 中从左到右第一个最大连续非零区间为 $a_{[u,v]}$ ，对 $a_{[u,v]}$ 做一次变换即可。
其他情况下，讨论 $x$ 的大小。
1. 当 $x=0$ 时，答案为 $1$ 。对 $a_{[1,n]}$ 做一次变换即可。
2. 当 $x=1$ 时，记这一个 $0$ 的下标为 $q$ 。先对 $a_{[1,q-1]}$ 做一次变换，再对 $a_{[q+1,n]}$ 做一次变换即可。答案为 $1$ 或 $2$ 。
3. 当 $x \geq 2$ 时，答案其实是 $2$ 。具体过程是先对 $a_{[1,n]}$ 做一次变换，再对 $a_{[1,n]}$ 做一次变换。第一次变换会将所有数变为 $\geq 1$ 的数，而第二次变换则会将所有数变为 $0$ 。