问题描述
题意：一个长度为 \(n\) 的由 \(-1\) 或 \(1\) 构成的序列 \(a\)，其中 \(1\) 的个数为 \(c\) 个。我们称一个子区间合法是指该子区间的数的和大于等于 \(0\)。求证：所有合法子区间的左端点的数量不超过 \(2c\) 个。
提示：子区间是指序列中连续的一段，形式化地说，问题是求证
\[\left|\left\{l:\exists_{r\geq l}\left(\sum_{i=l}^ra_i\right)\geq0\right\}\right|\leq2c \]举个例子，若 \(n=8,c=3\)，序列 \(a\) 为
\[-1,1,1,-1,-1,1,-1,-1 \]那么序列 \(a\) 中所有合法子区间的左端点共有 \(5\) 个，为下面括号的位置
\[(-1),(1),(1),-1,(-1),(1),-1,-1 \]解答
对于某个序列 \(a\)，记 \(S(a)\) 表示序列中所有合法子区间的左端点的数量。
如果 \(a\) 存在一个 \(-1\) 在一个 \(1\) 的后面，即存在下标 \(i,j\) 满足 \(i<j\) 且 \(a_i=1,a_j=-1\)，那么交换 \(i,j\) 位置上的值后，得到一个新序列 \(a'\)，显然 \(a'\) 中 \(1\) 的数量也为 \(c\)。
引理 进行上述变换后所有合法子区间的左端点的数量不降，即 \(S(a)\leq S(a')\) 一定成立。
假设上述引理成立，那么我们就只需要论证由 \(n-c\) 个 \(-1\) 开头，然后 \(c\) 个 \(1\) 组成的序列 \(a_0\) 满足 \(S(a_0)\leq 2c\)，这是显然的。而对于任何其他序列，它们都可以通过有限次上述变换得到序列 \(a_0\)。
下面我们证明该引理成立，考虑序列 \(a\) 的前缀和序列 \(p\)，
\[p_k=\sum_{i=1}^ka_i \]那么左开右闭区间 \((l..r]\) 合法等价于 \(p_r-p_l\geq0\)。设我们要交换序列 \(a\) 中的 \(i,j\) 位置，由于 \(a_i=1\)，所以 \(p_{i-1}=p_i-1\) 。若某个位置 \(k<i\) 本来某个合法区间的左端点，而交换 \(i,j\) 位置上的值后它就不是了，那么一定有 \(p_k=p_i\)。
那么找出 \(i\) 前面第一个 \(p_k=p_i\) 的位置（如果有）后，\(k\) 以前的左端点都不会改变，因为 \(p_k=p_i\) 说明 \(i,k\) 位置是等价的。这说明 \(S(a)\leq S(a')\)。
2022年12月08日 于东莞松山湖
标签：right,组合,leq,选讲,合法,区间,端点,序列,杂题 From： https://www.cnblogs.com/szdytom/p/combinatorial-misc-1.html