【题解】CF2077B Finding OR Sum

本文发布于博客园和洛谷，若您在其他平台阅读到此文，请前往博客园获得更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18771334。
思路

关于此题，我们首先对 \(n | x\) 变一下形，\(n | x = n + (x \& \sim n)\)，也就是把 \(n\) 和 \(x\) 同时为 \(1\) 的位在 \(x\) 中删掉，这样的话，为 \(1\) 的位要么在 \(n\)，要么在 \(x\)，因此我们可以得出 \((x \& \sim n) + (y \& \sim n) = (n | x) + (n | y) - 2 \times n\)。
我们要得到 \((m | x) + (m | y)\) 的值，只需要把每一位上 \(x\) 和 \(y\) 的 \(1\) 的出现数量情况找出来，再根据 \(m\) 的每一位是 \(1\) 还是 \(0\) 来模拟或运算以及位运算即可。
那么我们如何在两次询问的情况下，把每一位的 \(1\) 的出现数量找出来呢？
我们注意到，在二进制位的情况下相加，当前位为第 \(i\) 位，如果第 \(i + 1\) 位和 \(i - 1\) 位都是 \(0\)，则两个数的第 \(i\) 位相加只会有这两种情况：

• 两个 \(1\)：第 \(i + 1\) 位为 \(1\)，第 \(i\) 位为 \(0\)。
  
• 两个 \(0\)：第 \(i + 1\) 位和 第 \(i\) 位均为 \(0\)。
  
• 一个 \(1\) 一个 \(0\)：第 \(i\) 位为 \(1\)，第 \(i + 1\) 位为 \(0\)。
  

那么，我们就可以根据上面那个式子，求一次奇数位全部变成 \(0\) 的两个数的和，把偶数位的 \(1\) 的出现次数情况求出来，求一次偶数位全部变成 \(0\) 的两个数的和，把奇数位的 \(1\) 的出现次数情况求出来。
然后，根据下面的规则逐位求解：

• 如果 \(m\) 第 \(i\) 位为 \(1\)，那么这一位对答案的贡献就是 \(1 \ll (i + 1)\)。
  
• 如果 \(m\) 第 \(i\) 位为 \(0\)，那么这一位对答案的贡献就看 \(1\) 的出现次数，如果出现次数为 \(2\)，那就是 \(1 \ll (i + 1)\)，如果出现次数为 \(1\)，那就是 \(1 \ll i\)。
  

AC CODE

[code]#include #define inf 2e18#define int long longconst int N = 2e5 + 9;int ask(int x) {    std::cout  op;    return op;}void solve(){    std::vector a(30);    int tmp = 0;    for(int i = 0;i < 30;i += 2) {        tmp |= (1ll