题解

思路推导

只看非零元素。任何一个区间的交错和与区间中非零项的带符号贡献有关，而每个贡献都是 $1$ 或 $-1$。因此若非零元素个数为奇数，总贡献不可能为 $0$，必定无解。

若非零元素个数为偶数，按位置从左到右把它们两两配对。设一对非零元素位于 $l<r$。中间只有零，因此可以根据两端的符号和距离奇偶性，选择把 $[l,r]$ 作为一个区间，或者拆成 $[l,l]$ 与 $[l+1,r]$。这两种写法给第二个非零元素的符号相反，必有一种使这一对的总贡献为 $0$。未被配对区间覆盖的零单独成段即可。

做法

先统计并记录所有非零位置。若个数为奇数，输出 -1。否则依次处理相邻的两个非零位置，并用上面的两种划分之一抵消它们的贡献；配对区间之间以及末尾的零均输出为单点区间。

正确性证明

若非零元素数为奇数，所有区间交错和之和是奇数个 $1$ 或 $-1$ 的和，不可能等于 $0$，所以输出无解正确。

若非零元素数为偶数，算法把非零元素唯一地分成若干对。对于每一对，两种候选划分只改变第二个非零元素的贡献符号，因此其中恰有一种使这一对的贡献和为 $0$。所有零的贡献均为 $0$。算法输出的区间连续、互不重叠并覆盖整个数组，所以全部区间交错和的总和是各对贡献之和，即 $0$。因此算法输出的划分合法。

复杂度分析

每个测试用例的时间复杂度为 $O(n)$，额外空间复杂度为 $O(n)$；全部测试用例合计为 $O(\sum n)$。