题解：P13905 「KFCOI Round #2」宿命

暴力就是对于二进制下每一位分别维护，时间复杂度为

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})

。

f_{1}

也跟

f_{0}

差不多，自己推一下就知道了。

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

。

剩下就都是普通线段树的基本操作了，其他题解也放了代码，可以参考他们的。

题解：P13905 「KFCOI Round #2」宿命

文章操作

相关推荐

评论

题解：P13905 「KFCOI Round #2」宿命