题解：P13905 「KFCOI Round #2」宿命
j23wuyifan
·
·
题解
暴力就是对于二进制下每一位分别维护，时间复杂度为 O(n \log n \log V)。显然无法通过。
考虑优化，我们显然需要优化掉那个 \log V，所以不能将每一位都拆出来，要将其压回一个数。设计修改标记 f_{0},f_{1} 分别表示当前区间如果原来的数在这一位上是 0,1，修改后的值。接下来考虑如何下传标记。设当前节点的标记是 f_{0,x},f_{1,x}，其父亲节点下传的标记是 f_{0,y},f_{1,y}。先将每一维拆出来考虑：如果新的 f_{0,x} 当前这一位 u 是 1 有两种情况：
一：f_{0,y,u}=1 且 f_{1,x,u}=1。
二：f_{0,y,u}=0 且 f_{0,x,u}=1。
写成位运算就是：f_{0,nw,u} = (f_{0,y,u} \& f_{1,x,u}) | (\sim f_{0,y,u} \& f_{0,x,u})。
看成整体就是：f_{0,nw} = (f_{0,y} \& f_{1,x}) | (\sim f_{0,y} \& f_{0,x})。
```cpp
c.f0 = ((a.f0 & lim) & b.f1) | (((~a.f0) & lim) & b.f0);
c.f1 = ((a.f1 & lim) & b.f1) | (((~a.f1) & lim) & b.f0);
//lim=(1<<63)-1
```
接下来在考虑下传标记时对区间异或，或，与的值的影响。
```cpp
int both = p.f0 & p.f1;
int nand = both | (p.f1 & a.vand) | (p.f0 & ~a.vor);
int nor = both | (p.f1 & a.vor) | (p.f0 & ~a.vand);
int nxor;
if(a.len & 1)nxor = both | (p.f1 & (~p.f0) & a.vxor) | (p.f0 & (~p.f1) & (~a.vxor));
else nxor = a.vxor & (p.f0 ^ p.f1);
```
前两个都好理解，主要是异或。
如果 $len$ 是偶数：值是 $1$ 的位置肯定是 $f_{0},f_{1}$ 有一个在这一位是 $1$，且原来这位是 $1$。
如果 $len$ 是奇数：值是 $1$ 的位置肯定是 $f_{0},f_{1}$ 两位都是 $1$；或者只有 $f_{1}$ 是 $1$ 且原本这一位是 $1$；或者只有 $f_{0}$ 是 $1$ 且原本这一位是 $0$。
剩下就都是普通线段树的基本操作了，其他题解也放了代码，可以参考他们的。