Make Nonzero Sum (hard version)

题意翻译

给定一个长度为 $n$ 的，仅由 -1，0 或 1 组成的序列 $a$。你需要把它划分成若干个连续段，设这些连续段分别为 $[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$。 一个连续段 $[l_i,r_i]$ 的价值 $s_i=\sum_{j=l_i}^{r_i}(-1)^{j-l_i}a_j$。 这些连续段需要满足下列条件： - $l_1=1,r_k=n$。 - $\forall i\in \{1,2,\cdots,k-1\}, l_{i+1}=r_i+1$。 - $\sum_{i=1}^ks_i=0$。 请你给出一种合法的方案。若不存在合法方案，请输出 -1。$1\le n\le 2\times 10^5,\ a_i\in\{-1,0,1\}$。

题目描述

This is the hard version of the problem. The difference is that in this version the array contains zeros. You can make hacks only if both versions of the problem are solved. You are given an array $ [a_1, a_2, \ldots a_n] $ consisting of integers $ -1 $ , $ 0 $ and $ 1 $ . You have to build a partition of this array into the set of segments $ [l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k] $ with the following property: - Denote the alternating sum of all elements of the $ i $ -th segment as $ s_i $ : $ s_i $ = $ a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i} $ . For example, the alternating sum of elements of segment $ [2, 4] $ in array $ [1, 0, -1, 1, 1] $ equals to $ 0 - (-1) + 1 = 2 $ . - The sum of $ s_i $ over all segments of partition should be equal to zero. Note that each $ s_i $ does not have to be equal to zero, this property is about sum of $ s_i $ over all segments of partition. The set of segments $ [l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k] $ is called a partition of the array $ a $ of length $ n $ if $ 1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n $ and $ r_i + 1 = l_{i+1} $ for all $ i = 1, 2, \ldots k-1 $ . In other words, each element of the array must belong to exactly one segment. You have to build a partition of the given array with properties described above or determine that such partition does not exist. Note that it is not required to minimize the number of segments in the partition.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10\,000 $ ). Description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 200\,000 $ ) — the length of array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ a_i $ is $ -1 $ , $ 0 $ , or $ 1 $ ) — the elements of the given array. It's guaranteed that the sum of $ n $ over all test cases does not exceed $ 200\,000 $ .

输出格式

For each test case print an integer $ k $ — the number of segments in the partition. If required partition does not exist, print $ -1 $ . If partition exists, in the $ i $ -th of the following $ k $ lines print two integers $ l_i $ and $ r_i $ — description of the $ i $ -th segment. The following conditions should be satisfied: - $ l_i \le r_i $ for each $ i $ from $ 1 $ to $ k $ . - $ l_{i + 1} = r_i + 1 $ for each $ i $ from $ 1 $ to $ (k - 1) $ . - $ l_1 = 1, r_k = n $ . If there are multiple correct partitions of the array, print any of them.

输入输出样例

输入样例 #1

5
4
0 0 0 0
7
-1 1 0 1 0 1 0
5
0 -1 1 0 1
3
1 0 1
1
1

输出样例 #1

4
1 1
2 2
3 3
4 4
4
1 1
2 2
3 5
6 7
-1
2
1 1
2 3
-1

说明

In the first test case we can build a partition of $ 4 $ segments — each of them will contain only one element of the array equals to $ 0 $ . So the sum will be equal to $ 0 + 0 + 0 + 0 = 0 $ . In the second test case we can build a partition of $ 4 $ segments. The alternating sum of the first segment will be equal to $ -1 $ , the alternating sum of the second segment will be equal to $ 1 $ , of the third segment — $ 0 - 1 + 0 = -1 $ , of the fourth segment — $ 1 - 0 = 1 $ . The sum will be equal to $ -1 + 1 -1 + 1 = 0 $ . In the third test case it can be proved that the required partition does not exist.

**题目大意**：

给定一个长度为 $ n $ 的序列 $ a $，序列仅由 -1、0 或 1 组成。需要将序列划分成若干个连续段，例如 $[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$。

一个连续段 $[l_i,r_i]$ 的价值 $s_i$ 为该段内所有元素按位置奇偶性交替相加的和，即 $s_i=\sum_{j=l_i}^{r_i}(-1)^{j-l_i}a_j$。

这些连续段需要满足以下条件：

- $l_1=1,r_k=n$，即第一个段从序列开头开始，最后一个段到序列结尾结束。
- 对于任意 $i$ 属于 $\{1,2,\cdots,k-1\}$，都有 $l_{i+1}=r_i+1$，即前一个段的结束位置加一是下一个段的开始位置。
- 所有段的价值和 $\sum_{i=1}^ks_i=0$。

要求给出一种合法的划分方案，若不存在合法方案，则输出 -1。其中 $1\le n\le 2\times 10^5$，序列 $a$ 的元素 $a_i$ 只能是 $-1$、$0$ 或 $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$ 的元素。每个元素 $a_i$ 要么是 $-1$、$0$ 或 $1$。

**输出格式**：
- 对于每个测试用例，首先输出一个整数 $k$，表示划分的段数。如果不存在合法划分，则输出 $-1$。
- 如果存在合法划分，接下来 $k$ 行，每行输出两个整数 $l_i$ 和 $r_i$，描述第 $i$ 段的开始和结束位置。
- 要求满足以下条件：
- 对于每个 $i$ 从 $1$ 到 $k$，有 $l_i \le r_i$。
- 对于每个 $i$ 从 $1$ 到 $k-1$，有 $l_{i + 1} = r_i + 1$。
- $l_1 = 1, r_k = n$。

如果有多个正确的划分方案，输出其中任意一个即可。**题目大意**： 给定一个长度为 $ n $ 的序列 $ a $，序列仅由 -1、0 或 1 组成。需要将序列划分成若干个连续段，例如 $[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$。 一个连续段 $[l_i,r_i]$ 的价值 $s_i$ 为该段内所有元素按位置奇偶性交替相加的和，即 $s_i=\sum_{j=l_i}^{r_i}(-1)^{j-l_i}a_j$。 这些连续段需要满足以下条件： - $l_1=1,r_k=n$，即第一个段从序列开头开始，最后一个段到序列结尾结束。 - 对于任意 $i$ 属于 $\{1,2,\cdots,k-1\}$，都有 $l_{i+1}=r_i+1$，即前一个段的结束位置加一是下一个段的开始位置。 - 所有段的价值和 $\sum_{i=1}^ks_i=0$。 要求给出一种合法的划分方案，若不存在合法方案，则输出 -1。其中 $1\le n\le 2\times 10^5$，序列 $a$ 的元素 $a_i$ 只能是 $-1$、$0$ 或 $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$ 的元素。每个元素 $a_i$ 要么是 $-1$、$0$ 或 $1$。 **输出格式**： - 对于每个测试用例，首先输出一个整数 $k$，表示划分的段数。如果不存在合法划分，则输出 $-1$。 - 如果存在合法划分，接下来 $k$ 行，每行输出两个整数 $l_i$ 和 $r_i$，描述第 $i$ 段的开始和结束位置。 - 要求满足以下条件： - 对于每个 $i$ 从 $1$ 到 $k$，有 $l_i \le r_i$。 - 对于每个 $i$ 从 $1$ 到 $k-1$，有 $l_{i + 1} = r_i + 1$。 - $l_1 = 1, r_k = n$。 如果有多个正确的划分方案，输出其中任意一个即可。