对序列的构造题，区间操作可考虑通过前缀和或差分变成单点操作。
给定 \(n\) 个 0/1 变量 \(a_1\sim a_n\)，每次操作选定 \(i\)，将 \(a_i,a_{i+1},a_{i+2}\leftarrow a_i\oplus a_{i+1}\oplus a_{i+2}\)。构造一组方案使得 \(\leq n\) 操作内将所有 \(a_i\) 变成 \(0\)，或宣称无解。\(n\leq 2\times 10^5\)。
先写自己胡出来的分类讨论做法，顺序枚举首个遇到的全 \(1\) 极长序列 \([l,r]\)，按照长度奇偶性讨论：
- 长度为偶数：若 \(r\neq n\) 则可以通过操作 \(r-1,r-3\dotsc,l\) 消掉；若 \(r=n,l\neq 1\) 则可以通过操作 \(l-1,l+1\dotsc,r-2\) 消掉；若 \(l=1,r=n\) 无解。
- 长度为奇数：若 \(r\geq n-1\) 则无解；若 \(a_{r+2}=1\)，则对 \(r\) 操作消掉 \((1,0,1)\) 的部分，然后对于 \([l,r-1]\) 按照长度为偶数处理；若 \(a_{r+2}=0\)，则对 \(r\) 操作使其拓展为 \([l,r+2]\) 的奇数问题递归讨论。
不难证明这些情况可以给出所有合法的构造，且每次操作要么使两个 \(0\) 变为 \(1\)，要么使两个 \(1\) 变成 \(0\)，又因为每个数最多变动 \(2\) 次，故操作数严格小于 \(n\)。
正经做法是考虑前缀异或和。定义 \(s_i=\sum_{1\leq j\leq i} a_j\) 操作只会使 \(s_{i+1}\leftarrow s_{i-1},s_{i}\leftarrow s_{i+2}\)。最终的目标是让 \(s_1\sim s_n\) 均为 \(0\)。那么只需要在不同奇偶性中分别找到一个 \(s_i=0\) 的地方即可向两边扩展。
标签：leftarrow,奇偶性,CF1572B,leq,消掉,长度,操作 From： https://www.cnblogs.com/zhouzizhe/p/17842107.html