单种位运算

交换律:a@b=b@aa@b=b@a

结合律:a@(b@c)=(a@b)@ca@(b@c)=(a@b)@c

按位与/或

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

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

不存在逆运算

幂等律

a#a=aa\verb|#|a=a

单调性

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

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

操作数无关性

存在一个最大集合AAa,bA,a#b=ka,b\in A,a \verb|#| b =k

按位异或

单位元为00

自反

其逆运算即为自身

bb=0b\oplus b=0

复合位运算

分配律

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

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

应用

关于并运算的后缀最大值

定义下标从00开始,长度为nn的数组aa前缀最大值bb

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

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

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

由单调性可知iji\ge j

不妨假设我们已知j>kj> k的所有bjb_j,目的是求bkb_k

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

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

这样转移即可bk=max(ak,{buu=kd,dD})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