正题

题目链接:https://www.luogu.com.cn/problem/AT2382

---

题目大意

询问在$[L,R]$中选取一个或多个数，将它们按位或后能得到多少种不同的结果。

$1\le L\le R<2^{60}$

---

解题思路

我们先把高位的$L$和$R$都有的$1$都删除，因为它们之间的数都有这些$1$，显然没有用。

那么这样$L$和$R$的最高位就不同了，我们找到$R$的最高位$2^k$。

此时对于$[L,2^k)$中的数字都在$L$中，而且它们怎么或都不能超过$2^k$，所以这部分的答案就是$2^k-L$。

然后让这部分的数或上$2^k$，此时我们就有两个部分$[2^k,R]$和$[L+2^k,2^{k-1})$的数字。

先令$L=L+2^{k-1}$，然后我们分类讨论一下：

• $R\ge L-1$：此时$[2^k,2^{k-1})$都能直接有。
• $R\ge 2^k+2^{k-1}$：此时第$k-1$位为$0$的数都存在，然后我们让这一部分数或上$2^k+2^{k-1}$，那也能得到所有第$k-1$位为$1$的数，所以同上。
• $L<2^k+2^{k-1}$：此时$k-1$位为$1$的数都可以得到，继续考虑$k-1$位为$0$，对$k-2$位同上分类讨论即可。
• $R<2^k+2^{k-1},L\ge 2^k+2^{k-1}$：此时对于$k-1$位为$1$的部分我们显然不可能异或出比$L$小的数字，而比其大的数字都在，所以这部分答案是$2^k-L$,对$[2^k,R]$重新做一次上面的操作就好了。

时间复杂度：$O({\log }^{2}n)$

---

code

#include
#include
#include
#define ll long long
using namespace std;
ll A,B,ans;
signed main()
{
	scanf("%lld%lld",&A,&B);
	while(1){
		if(B<=1){
			ans+=B-A+1;
			printf("%lld\n",ans);
			return 0;
		}
		ll k=1ll;
		while(k*2ll<=B)k=k*2ll;
		if((A&k)&&(B&k))
		{A-=k,B-=k,k/=2ll;continue;}
		ans+=k-A;B-=k;k/=2ll;swap(A,B);
		while(k){
			if(A>B||A>=k){
				ans+=k*2ll;
				printf("%lld\n",ans);
				return 0;
			}
			if(B<k)ans+=k,k/=2ll;
			else{
				ans+=k*2ll-B;
				B=A;A=0;
				break;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37