P4424 [HNOI/AHOI2018]寻宝游戏
P4424 [HNOI/AHOI2018]寻宝游戏
太NT了，直接去想DP了，啥都没做出来，三十分滚了。
可以发现 \(x | 1 = 1\)，\(x \& 0 = 0\)，\(x \& 1 = x\)，\(x | 0 = x\)。那么我们可以把操作序列看作是 \(01\) 串。 \(\& \rightarrow 1\)，\(| \rightarrow 0\) 那么当操作序列和数字序列相等时，答案不变，恒为初始值。那么我们可以按位拆开来算，第 \(N\) 行 \(j\) 位为最高位，一共 \(N\) 位 \(M\) 个数字。合并不等式范围。
设操作序列为 \(op\)，数字序列为 \(x\)。
当 \(op \lt x\) 那么答案为 \(0\) 考虑他们是第 \(i\) 位产生不同且 \(op_i \lt x_i\) 所以 \(op_i = 0,x_i = 1\) 也就是 \(|1\) 所以最后一个必为 \(1\)，对于 \(i+1 \text{~} N\) 位因为相等，所以不影响答案。
当 \(op \gt x\) 那么答案为 \(1\) 考虑他们是第 \(i\) 位产生不同且 \(op_i \gt x_i\) 所以 \(op_i = 1, x_i = 0\) 也就是 \(\&0\) 所以最后一个必为 \(0\)，对于 \(i+1\text{~}N\) 位因为相等，所以不影响答案。
\[\begin{cases} upper\_bound = min_{s_i = 1}\{ rk_i \} \\ lower\_bound = max_{s_i = 0}\{ rk_i \} \end{cases} \]所以对于询问串 \(q\) ，如果 \(q_i = 0\) 限定了 \(op\) 的上界，\(q_i=1\) 限定了 \(op\) 的下界。所以用最小的上界减去最大的下界就完了。注意当上届位 \(rk[M+1]\) 时，答案要加 \(1\)。具体看代码。
/*
Name:
Author: Gensokyo_Alice
Date:
Description:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include