CF1753A2 Make Nonzero Sum (hard version)

这是该问题的困难版本。不同之处在于本版本的数组中包含 $0$。只有当你同时解决了两个版本的问题时，才能进行 hack。 给定一个由 $-1$、$0$ 和 $1$ 组成的数组 $[a_1, a_2, \ldots, a_n]$。你需要将该数组划分为若干个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$，使其满足以下性质： - 记第 $i$ 个区间的交错和为 $s_i$：$s_i = a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$。例如，对于数组 $[1, 0, -1, 1, 1]$，区间 $[2, 4]$ 的交错和为 $0 - (-1) + 1 = 2$。 - 所有区间的 $s_i$ 之和应等于 $0$。 注意，每个 $s_i$ 不必等于 $0$，只要求所有 $s_i$ 的和为 $0$。 区间集合 $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ 被称为长度为 $n$ 的数组 $a$ 的一个划分，当且仅当 $1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$，且对于所有 $i = 1, 2, \ldots, k-1$，都有 $r_i + 1 = l_{i+1}$。换句话说，数组中的每个元素必须且仅属于一个区间。 你需要构造一个满足上述性质的划分，或者判断不存在这样的划分。 注意，不要求划分的区间数最小。

每组测试数据包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10\,000$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$a_i$ 取 $-1$、$0$ 或 $1$），表示给定的数组。 保证所有测试用例中 $n$ 的总和不超过 $200\,000$。

对于每组测试用例，输出一个整数 $k$，表示划分的区间数。如果不存在满足要求的划分，输出 $-1$。 如果存在划分，接下来的 $k$ 行中，第 $i$ 行输出两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个区间。需满足以下条件： - 对于每个 $i$，$l_i \le r_i$。 - 对于每个 $i$ 从 $1$ 到 $k-1$，有 $l_{i+1} = r_i + 1$。 - $l_1 = 1, r_k = n$。 如果存在多种合法划分，输出任意一种即可。

在第一个测试用例中，可以将数组划分为 $4$ 个区间，每个区间只包含一个 $0$ 元素。这样交错和之和为 $0 + 0 + 0 + 0 = 0$。 在第二个测试用例中，可以将数组划分为 $4$ 个区间。第一个区间的交错和为 $-1$，第二个区间为 $1$，第三个区间为 $0 - 1 + 0 = -1$，第四个区间为 $1 - 0 = 1$。所有交错和之和为 $-1 + 1 - 1 + 1 = 0$。 在第三个测试用例中，可以证明不存在满足要求的划分。 由 ChatGPT 4.1 翻译