题解：[ARC153C] ± Increasing Sequence （加强版）

这个 $A_i\in \{ -1,1\}$ 太逊了，我们看看丢掉这个条件能不能做。

考虑使用差分数组刻画限制：

设 $B_i$ 为 $A_i$ 的后缀和，则题目条件可以表示为 $\sum B_ic_i=0$。

此外，我们还有一个 $\forall i>1,c_i>0$ 的要求，我们对 $c_1$ 的大小没有要求，考虑从此处入手。接下来我们分两种情况讨论：

不妨设 $B_1>0$，否则可以全部取反。

现在 $c_1=-\sum_{i=2}^n B_i, c_i=B_1$ 满足要求。

相当于说现在 $c_1$ 没用了，直接设为 $0$。

先把 $\forall i, B_i=0$ 的情况特判掉。

我们发现，如果剩下的 $B_i$ 都有 $B_i\le 0$，则最终的和一定小于 $0$，反之同理。

所以我们现在能找到一个 $B_{x}>0$ 和一个 $B_y<0$。

设 $s=B_x+B_y-\sum B$，不妨认为 $s>0$，则 $c_x=B_x-\sum B, c_y=B_x, c_i=B_x$ 为一组合法解，否则 $c_x=-B_y, c_y=\sum B- B_y, c_i=B_i$ 为一组合法解。

这样我们就成功地构造出来了答案。