P4428:[BJOI2018]二进制 – 题解

主要思路

打个表发现合法的区间需要满足以下条件之一:

  • 如果区间内的 \(1\) 的个数为奇数,则至少要有 \(2\) 个 \(0\)。
  • 区间内的 \(1\) 的个数为偶数。

我们可以考虑维护不合法的区间,因为不合法的区间特征明显一点,只有这种:

  • 如果区间内的 \(1\) 的个数为奇数,且 \(0\) 的个数 \(< 2\)。

我们可以考虑用线段树来维护这个信息。大概就是需要固定左右端点的选择,然后再用分治的方法处理跨两个子树的区间即可。

继续阅读P4428:[BJOI2018]二进制 – 题解