闲话 3.5

原来想的太复杂了，，而且是假的

证明：设长度为 \(n\) 的序列有等量 \(1,-1\)，并且可以成环。那么必存在一个位置，这个位置开始的最小前缀和 \(\ge -1\)。

对此施加结构归纳。设 \(A\) 序列和 \(B\) 序列接在一起（这两个序列分别具有等量 \(1,-1\)），考察其新产生的最小值（原来两个序列的开头开始的最小值记为 \(A,B\)）。

从 \(A\) 的某个位置开始，经过 \(B\) 的某个位置，则此时的前缀最小值为：\(-sA_i+B\)。从 \(B_i\) 开始同理。

从 \(A\) 的某个位置开始，跨过整个 \(B\) 再回来，和没有跨过是一样的。因此，如果 \(A,B\) 不是各自唯一 \(\ge -1\) 的方案，就存在至少另外的方案使其成立。在这情况下从 \(A\) 的开头开始即可，前缀最小值不超过 \(\min(A,B)=-1\)。

最后考察不能被分割的串。这样的串一定形如 \(A_1 B_1 A_2 B_2\dots\)（\(A\) 是 \(1\) 连通块长度，\(B\) 是 \(-1\) 连通块长度），并且要么 \(A_i>B_i\)，要么 \(A_i<B_i\)（除了最后一个）。

那么 \(A_i>B_i\) 从开始走，\(A_i<B_i\) 从最后的 \(A\) 开头开始走即可。