P3514 [POI2011] LIZ-Lollipop

很神奇的题

题意：给你一个由 \(0\) 和 \(1\) 组成的序列，给出 \(q\) 个询问，每次询问是否有原序列是否有总和为 \(x\) 的子段。

考虑递推，但是小答案对大答案的影响不好算。

考虑大区间对小区间的影响。

设当前区间为 \([l,r]\) ,总和为sum，有 \(4\) 种情况

1. \(a[l]=2,a[r]=2\);这是无论是把左端点往右移动一个单位，或是把右端点往左移动一个单位，sum-2都能被构造出来
2. \(a[l]=2,a[r]=1\); 把左端点往右移动一个单位，sum-2能被构造出来
3. \(a[l]=1,a[r]=2\); 把右端点往左移动一个单位，sum-2能被构造出来
4. \(a[l]=1,a[r]=1\);左端点往右移动一个单位，并把右端点往左移动一个单位，sum-2能被构造出来

所以，当我们找到一个能被构造的最大的偶数，比他小的所有偶数都能被构造出来。当我们找到一个能被构造的最大的奇数，比他小的所有奇数都能被构造出来。

再思考一下发现所有可能的构造方案都已经被上面的情况包含了。

最后的问题是怎么找最大的偶数、奇数。显然其中有一个数是 \(sum[n]\). 因为\(sum[n]\)要减去一个奇数才能改变奇偶性，所以找到最左边的 \(1\)，和最右边的 \(1\)。减去其前缀/后缀，就找到了最大的奇数/偶数。