单种位运算

交换律：$a@b=b@a$

结合律：$a@(b@c)=(a@b)@c$

按位与/或

下文按位与/或统称$\verb|#|$

单位元为$11..11_{(2)}$/$0$

不存在逆运算

幂等律

$a\verb|#|a=a$

单调性

$a\verb|&|b\le \min(a,b)$

$a\verb|||b\ge \max(a,b)$

操作数无关性

存在一个最大集合$A$，$a,b\in A,a \verb|#| b =k$

按位异或

单位元为$0$

自反

其逆运算即为自身

$b\oplus b=0$

复合位运算

分配律

$a\verb|&|(b\verb|||c)=(a\verb|&|b)|(a\verb|&|c)$

$a\verb|^|(b\verb|||c)=(a\verb|^|b)|(a\verb|^|c)$

应用

关于并运算的后缀最大值

定义下标从$0$开始，长度为$n$的数组$a$前缀最大值$b$为

$b_j=\max(\{a_i|0\le i < j\})$

对下标并运算的前缀最大值

$b_j=\max(\{a_i|i\&j=j\})$

由单调性可知$i\ge j$

不妨假设我们已知$j> k$的所有$b_j$，目的是求$b_k$

我们知道前缀和符合交换律和结合律

那么定义集合$D=\{1,10_{2},10_{2},100_{2},...10_{(2)}^{\lceil\log(n)\rceil}\}$

这样转移即可$b_k=\max(a_k,\{b_u|u=k或运算d,d\in D\})$

例题

2021“MINIEYE杯”中国大学生算法设计超级联赛（2）—I love max and multiply

https://acm.hdu.edu.cn/showproblem.php?pid=6971