概述

本题给出一个只含 ~-1~、~0~、~1~ 的数组，要求把每个 ~-1~ 替换成 ~0~ 或 ~1~，使数组的分数（两端为 ~1~、中间全为 ~0~ 的子数组的最大长度）达到最大。核心结论是：只需把「第一个 ~1~ 之前最靠左的那个 ~-1~」与「最后一个 ~1~ 之后最靠右的那个 ~-1~」改成 ~1~，其余 ~-1~ 一律改成 ~0~，两次线性扫描即可完成。

分析

核心观察

数组的分数只由其中所有 ~1~ 的位置决定。把值为 ~1~ 的下标从小到大记为 ~p_1 < p_2 < \ldots < p_r~，则当 ~r \ge 2~ 时

$$\displaystyle \mathrm{score}(b) = \max_{1 \le j < r} \left( p_{j+1} - p_j + 1 \right) $$

即相邻两个 ~1~ 的距离的最大值；~r = 1~ 时分数为 ~1~，~r = 0~ 时分数为 ~0~。原因是：子数组「两端为 ~1~、内部全为 ~0~」与「两端是这个数组中相邻的两个 ~1~」是一一对应的——只要两个 ~1~ 之间没有别的 ~1~，把中间的元素全部取成 ~0~ 就得到合法子数组；反之合法子数组的两端之间不可能还有 ~1~。

思路

只有 ~-1~ 的位置可以自由选择，因此把问题放宽成两个集合：记 ~C~ 为可以放 ~1~ 的位置（即 ~a_i \ne 0~ 的下标），记 ~F~ 为固定是 ~1~ 的位置（即 ~a_i = 1~ 的下标）。任何一种替换方案最终得到的 ~1~ 位置集合 ~S~ 都满足 ~F \subseteq S \subseteq C~，反过来任意这样的 ~S~ 都能由一种替换方案实现。

上界。 设某组方案里分数由相邻的两个 ~1~ ~i < j~ 取得，则 ~i, j \in C~，且开区间 ~(i, j)~ 内没有任何 ~1~，自然也没有 ~F~ 中的位置。反过来，任取一对满足

1. ~i < j~，且 ~i, j \in C~（两端都可以放 ~1~）；
2. 开区间 ~(i, j)~ 内没有 ~F~ 中的位置（中间没有本来就固定的 ~1~）

的下标，都能构造出一组方案：只把 ~i~、~j~ 改成 ~1~，区间内部与外部的 ~-1~ 全部改成 ~0~。此时 ~i~、~j~ 是相邻的两个 ~1~，分数至少为 ~j - i + 1~。于是最优分数恰好等于「所有满足上述两条的区间 ~[i, j]~ 的最大长度」（单个位置 ~i = j~ 也是一种候选，长度为 ~1~；若 ~C~ 为空则分数为 ~0~）。

构造。 下面这组替换可以达到这个上界：

• 从左往右找到第一个不是 ~0~ 的位置 ~i_0~（即最靠左的可放 ~1~ 的位置）。若 ~a_{i_0} = -1~，把它改成 ~1~；若它本来就是 ~1~，不动。
• 对称地，从右往左找到第一个不是 ~0~ 的位置 ~j_0~。若 ~a_{j_0} = -1~，把它改成 ~1~。
• 其余的 ~-1~ 一律改成 ~0~。

「第一个 ~1~ 之前最靠左的 ~-1~」就是第一个非零位置 ~i_0~（当它不是 ~1~ 时），右侧同理，所以上面的说法与题解结论一致。

正确性说明。 记构造后 ~1~ 的位置集合为 \(S^\*\)。任取一个候选区间 ~[i, j]~，证明 \(S^\*\) 中存在距离不小于 ~j - i + 1~ 的一对相邻 ~1~。

• 若数组中本来没有 ~1~：所有可放 ~1~ 的位置都是 ~-1~，最外侧的两个候选位置就是 ~i_0~ 与 ~j_0~，候选区间的最大长度即 ~j_0 - i_0 + 1~，而构造恰好把这两个位置置为 ~1~、中间全置 ~0~，分数正好取到这个值。
• 否则设 ~f~ 为第一个原来的 ~1~、~l~ 为最后一个原来的 ~1~。
  • 若 ~i < f~：由 ~i \in C~ 知 ~i~ 是 ~f~ 之前的一个 ~-1~，故 ~i_0 \le i~。而 ~i_0~ 与 ~f~ 之间没有原来的 ~1~（~f~ 是第一个），中间的 ~-1~ 也不会被构造置 ~1~（它们既不是最左的 ~i_0~，也不在最右的 ~j_0~ 之右），所以 ~i_0~ 与 ~f~ 在 \(S^\*\) 中相邻，分数至少为 ~f - i_0 + 1 \ge f - i + 1 \ge j - i + 1~。最后一步用了 ~j \le f~：若 ~j > f~，则 ~f~ 是区间 ~(i, j)~ 内固定的 ~1~，与候选区间的条件矛盾。
  • 若 ~i \ge f~ 且 ~j > l~：与上一条完全对称，~j_0 \ge j~，且 ~l~ 与 ~j_0~ 在 \(S^\*\) 中相邻，分数至少为 ~j_0 - l + 1 \ge j - l + 1 \ge j - i + 1~。这里 ~\ge~ 用到了 ~i \ge l~：若 ~i < l~，则固定的 ~1~ ~l~ 落在区间 ~(i, j)~ 内（因为 ~j > l~），与候选区间的条件矛盾。
  • 若 ~i \ge f~ 且 ~j \le l~：取 ~u~ 为不超过 ~i~ 的最后一个原来的 ~1~、~v~ 为不小于 ~j~ 的第一个原来的 ~1~（由 ~f \le i~ 与 ~j \le l~ 知二者存在）。区间 ~(i, j)~ 内没有固定的 ~1~，所以 ~u~ 与 ~v~ 是原来的 ~1~ 中相邻的两个；又 ~(u, v)~ 内的 ~-1~ 都不会被构造置 ~1~（它们既不是最左的 ~i_0~，也不是最右的 ~j_0~），所以 ~u~、~v~ 在 \(S^\*\) 中相邻，分数至少为 ~v - u + 1 \ge j - i + 1~。

单个位置的候选 ~i = j~ 也成立：只要 ~C~ 非空，构造后至少有一个 ~1~，分数至少为 ~1~。综上，构造得到的分数不小于任何候选区间的长度，即达到最优。

具体示例

• 第三组 ~a = [-1, 0, 0, -1, 0]~：没有原来的 ~1~，最左、最右的可放 ~1~ 位置分别是第 ~1~ 位与第 ~4~ 位，把它们改成 ~1~、中间全改成 ~0~，得到 ~[1, 0, 0, 1, 0]~，分数为 ~4~。不存在比它们更靠外的可放 ~1~ 位置，因此最优分数就是 ~4~。
• 第六组 ~a = [1, 0, 1, 0, 0, -1]~：最左的非零位置本身就是 ~1~（不动）；最右的非零位置是第 ~6~ 位的 ~-1~，改成 ~1~，得到 ~[1, 0, 1, 0, 0, 1]~，分数为 ~4~（第 ~3~ 位到第 ~6~ 位）。
• 第八组 ~a = [-1, -1, -1, -1, -1, -1]~：两端置 ~1~、中间置 ~0~，得到 ~[1, 0, 0, 0, 0, 1]~，分数为 ~6~；整个数组只有 ~6~ 个元素，分数不可能超过 ~6~，故这是最优解。
• 第九组 ~a = [-1, 0, 1, -1, 0, 0, 1]~：最左的非零位置是第 ~1~ 位的 ~-1~，改成 ~1~；最右的非零位置是第 ~7~ 位的 ~1~，不动；第 ~4~ 位的 ~-1~ 改成 ~0~，得到 ~[1, 0, 1, 0, 0, 0, 1]~，分数为 ~5~（第 ~3~ 位到第 ~7~ 位）。样例给出的参考输出是 ~[0, 0, 1, 0, 0, 0, 1]~，分数同样是 ~5~——最优解不唯一，本题由 special judge 判定。

算法步骤

1. 读入测试用例个数 t。
2. 对每个测试用例，读入长度 n 与数组 a。
3. 从左往右扫描 a：若当前位置是 ~-1~，把它改成 ~1~ 并结束扫描；若当前位置是 ~1~，直接结束扫描；若当前位置是 ~0~，继续看下一个位置。
4. 从右往左扫描 a：规则与上一步相同。
5. 输出 n 个整数，其中仍等于 ~-1~ 的元素写成 ~0~（等价于输出 a[i] 与 ~0~ 的较大值）。

复杂度分析

• 时间：每个测试用例只做两次扫描，~O(n)~；全部测试用例合计 ~O(\sum n)~，而 ~\sum n \le 2 \times 10^5~。
• 空间：~O(n)~，用于存储数组 ~a~。

实现注意事项

• 两次扫描相互独立：每次扫描最多改动一个位置，谁先谁后、会不会被另一次扫描看到，都不影响结果。
• 扫描在遇到 ~1~ 时必须立即结束。若越过这个 ~1~ 继续把后面的 ~-1~ 也改成 ~1~，会把原本连续的长区间切断，分数反而变小——输出仍然合法，但会因不是最优解被 special judge 判错。
• 输出中不能残留 ~-1~：没有参与两次扫描的 ~-1~ 必须在输出时写成 ~0~，否则 checker 会以「非 ~-1~ 位置与原数组不符 / ~-1~ 位置必须为 0 或 1」为由判错。
• 边界：~n = 1~ 且 ~a_1 = -1~ 时，左扫描把它改成 ~1~，右扫描遇到 ~1~ 直接结束，输出 ~1~，分数为 ~1~。
• 全部为 ~0~ 时没有任何位置可以放 ~1~，两次扫描都不改动元素，输出全 ~0~，分数为 ~0~。
• 输入总量为 ~\sum n \le 2 \times 10^5~ 个整数，直接使用 cin / cout 即可，加上 ios::sync_with_stdio(false) 更稳妥；注意每个测试用例单独输出一行。

源代码

#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> a[i];
        }

        // 左侧：第一个非零位置若是 -1，就置为 1
        for (int i = 0; i < n; ++i) {
            if (a[i] == -1) {
                a[i] = 1;
            }
            if (a[i] == 1) {
                break;
            }
        }

        // 右侧：对称处理
        for (int i = n - 1; i >= 0; --i) {
            if (a[i] == -1) {
                a[i] = 1;
            }
            if (a[i] == 1) {
                break;
            }
        }

        // 其余 -1 输出为 0
        for (int i = 0; i < n; ++i) {
            std::cout << (a[i] > 0 ? a[i] : 0) << (i + 1 == n ? '\n' : ' ');
        }
    }

    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    pos = 0
    t = int(data[pos])
    pos += 1
    out = []

    for _ in range(t):
        n = int(data[pos])
        pos += 1
        a = [int(x) for x in data[pos:pos + n]]
        pos += n

        # 左侧：第一个非零位置若是 -1，就置为 1
        for i in range(n):
            if a[i] == -1:
                a[i] = 1
            if a[i] == 1:
                break

        # 右侧：对称处理
        for i in range(n - 1, -1, -1):
            if a[i] == -1:
                a[i] = 1
            if a[i] == 1:
                break

        # 其余 -1 输出为 0
        out.append(" ".join(str(x if x > 0 else 0) for x in a))

    sys.stdout.write("\n".join(out) + "\n")


main()