CF1798E Multitest Generator

我们称一个数组 $b_1, b_2, \ldots, b_m$ 是一个 test，当且仅当 $b_1 = m - 1$。 我们称一个数组 $b_1, b_2, \ldots, b_m$ 是一个 multitest，当且仅当数组 $b_2, b_3, \ldots, b_m$ 可以被划分为 $b_1$ 个非空连续子数组，并且每个子数组都是一个 test。注意，每个元素必须恰好属于一个子数组，且子数组必须由连续的元素组成。 我们定义函数 $f$，对于数组 $b_1, b_2, \ldots, b_m$，$f$ 表示将该数组变为 multitest 所需的最少操作数。每次操作可以“将任意 $b_i$ 替换为任意非负整数 $x$”。 给定一个正整数数组 $a_1, a_2, \ldots, a_n$。对于每个 $i$ 从 $1$ 到 $n-1$，求 $f([a_i, a_{i+1}, \ldots, a_n])$。 下面是一些 test 和 multitest 的示例。 - test 示例：$[\underline{1}, 5]$，$[\underline{2}, 2, 2]$，$[\underline{3}, 4, 1, 1]$，$[\underline{5}, 0, 0, 0, 0, 0]$，$[\underline{7}, 1, 2, 3, 4, 5, 6, 7]$，$[\underline{0}]$。这些数组都是 test，因为它们的第一个元素（下划线标记）等于数组长度减一。 - multitest 示例：$[1, \underline{\underline{1}, 1}]$，$[2, \underline{\underline{3}, 0, 0, 1}, \underline{\underline{1}, 12}]$，$[3, \underline{\underline{2}, 2, 7}, \underline{\underline{1}, 1}, \underline{\underline{3}, 4, 4, 4}]$，$[4, \underline{\underline{0}}, \underline{\underline{3}, 1, 7, 9}, \underline{\underline{4}, 2, 0, 0, 9}, \underline{\underline{1}, 777}]$。下划线部分为分割后的子数组，双下划线为每个子数组的第一个元素。

每个测试包含多组测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 300\,000$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 300\,000$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 300\,000$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $300\,000$。

对于每组测试用例，输出 $n-1$ 个数，依次表示 $f([a_i, a_{i+1}, \ldots, a_n])$，$i$ 从 $1$ 到 $n-1$。

在第一个测试的第一个用例中，数组 $[1, 2, 1, 7]$ 是一个 multitest，因为 $[2, 1, 7]$ 是一个 test。数组 $[2, 1, 7]$ 不是 multitest，但将第一个数替换为 $1$ 后，得到 $[1, 1, 7]$，它是一个 multitest。因此 $f([2, 1, 7]) = 1$。数组 $[1, 7]$ 也不是 multitest，但 $[1, 0]$ 是 multitest，所以 $f([1, 7]) = 1$。 在第一个测试的第二个用例中，对于 $i=2$，$f([a_i, a_{i+1}, \ldots, a_n]) = f([1, 3, 1, 2, 1, 1]) = 1$，因为该数组本身不是 multitest，但将第二个元素替换为 $4$ 后可以得到 multitest。 在第一个测试的第三个用例中，对于 $i=1$，$f([a_i, a_{i+1}, \ldots, a_n]) = f([2, 7, 1, 1]) = 1$，因为该数组本身不是 multitest，但将第二个元素替换为 $0$ 后可以得到 multitest。 第二个测试用例是由第一个测试用例所有数字组成的数组。因此 $f([a_1, a_2, \ldots, a_n])$ 显然等于 $0$。 由 ChatGPT 4.1 翻译