题解 AT2382 【[AGC015D] A or...or B Problem】

zhimao · 2021-01-18 21:05:17 · 题解

思路和官方题解一样 。 首先特判掉 l=r 的情况 , 否则我们可以找出 l 与 r 在二进制下最高的不同位 。 就像这样 ：

1100...0    1     001...1 -> r
1100...0    0     101...0 -> l
  相同  最高不同位 剩下位

则最高位 r 必为 1 。此时我们再引入另一个数 z ,

1100...0    1     001...1 -> r
1100...0    0     101...0 -> l
  相同  最高不同位 剩下位

1100...0    1     000...0 -> z
                   都为零

则我们可以把 [l,r] 拆为 [l,z) 与 [z,r] 。 分开讨论 。

2. ``` 1100...0 1 00 1...1 -> p 相同 最高不同位 剩下位 都是一 ```

可证明只能运算得到 [z,p] ， 我们可以找出这样的数

1100...0    1       00   1 0...0 -> x1
  相同  最高不同位 剩下位   为零 
1100...0    1       00   01 0...0 -> x2
  相同  最高不同位 剩下位    为零 
1100...0    1       00   001 0...0 -> x3
  相同  最高不同位 剩下位     为零 
......
1100...0    1       00   0...0 1 -> xn
  相同  最高不同位 剩下位 为零 

可拼出 [z,p] ， 因为 or 运算不会进位 ， 所以拼不出其他的了 。

3. 两个区间的数相互运算 ， 则为 [l|z,z|(z-1)] 证法与上雷同 ， 就不写了 。

代码

#include<bits/stdc++.h>
using namespace std;
long long x,y,ans;
int main()
{
    scanf("%lld%lld",&x,&y);
    if(x==y)
    {
        puts("1");
        return 0;
    }
    long long z=y,j=0;
    for(int i=1;(1ll<<i)<=y;i++)
        if((((x&y)>>i)&1)!=(((x|y)>>i)&1)) 
        {
            z>>=i;
            z<<=i;
            j=i;
        }
    ans=z-x;
    long long l1=z,r1=z,l2=x|z,r2=z|(z-1);
    for(int i=j-1;i>=0;i--)
        if(y&(1ll<<i))
        {
            r1|=(1ll<<(i+1))-1;
            break;
        }
    if(r1<l2) ans+=r1-l1+r2-l2+2; else ans+=r2-l1+1;
    printf("%lld",ans);
    return 0;
}