题意
定义一个序列 \(b_1, b_2, b_3, \cdots, b_m\) 为 \(\texttt{test}\) 当且仅当 \(b_1 = m - 1\)。
定义一个序列 \(b_1, b_2, b_3, \cdots, b_m\) 为 \(\texttt{multitest}\) 当且仅当该序列可以划分为 \(b_1\) 段子串，且每段子串均为一个 \(\texttt{test}\)。
现给定一个长度为 \(n\) 的正整数序列 \(a_1, a_2, a_3, \cdots, a_n\)，对于所有的 \(i \in \left[1, n\right)\)，求出使原序列的后缀 \(a_i, a_{i + 1}, \cdots, a_n\) 为 \(\texttt{multitest}\) 的最小修改次数（每次修改可以更改一个元素，不可以删减元素）。
（\(1 \le n \le 3 \times 10^5\)）。
题解
首先考虑一个性质
对于任意序列，均可以通过 \(2\) 次更改使其成为 \(\texttt{multitest}\)。
假设我们有任意序列 \(b_1, b_2, b_3, \cdots, b_m\)，执行操作 \(b_1 \leftarrow 1, b_2 \leftarrow m - 2\) 即可使其成为 \(\texttt{multitest}\)。
那么我们只需要考虑当前序列能否通过小于 \(2\) 次操作使其变为 \(\texttt{multitest}\)。
首先考虑 \(0\) 次操作，即当前序列原始就是一个 \(\texttt{multitest}\)。
记 \(f_i\) 表示 \(i\) 的后缀能构成的连续合法 \(\texttt{test}\) 的个数，可以得出转移方程如下：
\[f_i = \begin{cases} 1 & i + a_i + 1 = n + 1 \\ 0 & i + a_i + 1 > n + 1 \lor f_{i + a_i + 1} = 0\\ f_{i + a_i + 1} + 1 & \text{otherwise} \end{cases}\]可以发现 \(f\) 的值可以 \(\mathcal{O}(n)\) 求出。第 \(i\) 位的答案为 \(0\) 的充要条件为 \(f_{i + 1} = a_i\)。
接下来考虑 \(1\) 次操作，如果 \(i + 1\) 的后缀可以形成合法的若干 \(\texttt{test}\) 即 \(f_{i + 1} > 0\)，那么直接执行更改 \(a_i \leftarrow f_{i + 1}\) 即可。
如果 \(i + 1\) 的后缀无法形成合法的 \(\texttt{test}\)，那么考虑在该后缀中进行更改。可以发现一个性质
如果一个序列可以通过 \(1\) 次更改形成 \(k\) 个合法 \(\texttt{test}\)，那么其一定可以通过 \(1\) 次更改形成 \(k^{\prime} \le k\) 个 \(\texttt{test}\)。
考虑改变原始更改方案。设在该方案中改变了 \(a_t\) 的值，在此之后的若干 \(\texttt{test}\) 的首位元素下标为 \(c_1, c_2, \cdots\)，其中 \(a_t = c_0\)，那么我们只需要执行 \(a_t \leftarrow c_{k - k^{\prime}} - 1\) 即可。若在此之后的 \(\texttt{test}\) 数量小于 \(k - k^{\prime}\)，那么我们更改从后往前数第 \(k - k^{\prime} + 1\) 个 \(\texttt{test}\) 的首位元素即可。
所以我们只需要求出在 \(i\) 的后缀中通过 \(1\) 次更改可以形成的最多合法 \(\texttt{test}\) 数量 \(g_i\) 即可判定。若 \(a_i \le g_{i + 1}\)，那么结合上文性质可得第 \(i\) 位的答案为 \(1\)。
下面考虑如何求出 \(g_i\) 的值，考虑两种转移
- 改变 \(a_i\) 的值，那么因为可以任意更改当前 \(\texttt{test}\) 的长度即下一个 \(\texttt{test}\) 的首位元素且之后不能再次执行更改，所以在所有的可能首位元素中取 \(f\) 最大值即可，此时 \(\displaystyle g_i = \max\limits_{j = i + 1}^{n + 1} f_{j} + 1\)；
- 不改变 \(a_i\) 的值，那么下一个 \(\texttt{test}\) 的首位元素为 \(i + a_i + 1\)，且之后可以进行更改，故从 \(g_{i + a_i + 1}\) 转移即可，即 \(g_i = g_{i + a_i + 1}\)。
两种情况取最大值即可推出 \(g_i\) 的值，利用后缀最大值优化即可以 \(\mathcal{O}(n)\) 的复杂度处理 \(f, g\) 两个数组的值。
Code
//Codeforces - 1798E
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
constexpr valueType MIN = INT_MIN >> 2;
int main() {
valueType T;
std::cin >> T;
for (valueType testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
ValueVector source(N + 2), next(N + 2, N + 2), F(N + 2, MIN), G(N + 2, MIN), maxF(N + 2, MIN);
for (valueType i = 1; i <= N; ++i) {
std::cin >> source[i];
next[i] = i + source[i] + 1;
}
maxF[N + 1] = F[N + 1] = G[N + 1] = 0;
for (valueType i = N; i > 1; --i) {
if (next[i] <= N + 1)
F[i] = F[next[i]] + 1;
G[i] = maxF[i + 1] + 1;
if (next[i] <= N + 1)
G[i] = std::max({G[i], G[next[i]] + 1});
maxF[i] = std::max(maxF[i + 1], F[i]);
}
for (valueType i = 1; i < N; ++i) {
if (source[i] == F[i + 1]) {
std::cout << 0 << ' ';
} else if (F[i + 1] > 0 || G[i + 1] >= source[i]) {
std::cout << 1 << ' ';
} else {
std::cout << 2 << ' ';
}
}
std::cout << '\n';
}
std::cout << std::flush;
return 0;
}