【luogu AT2382】A or...or B Problem（思维）

A or…or B Problem

题目链接：luogu AT2382

题目大意

给你一个区间，问里面的数你至少选一个，可以通过或得到多少个数。

思路

考虑一些东西，至少是二进制。
然后想一下会发现高位一样的都可以当 $0$，就只用从第一个不一样的地方开始看（如果一样就大小为 $1$）

然后就分割成两个部分的数，考虑分开处理，分别是到 $\mathrm{10...}$ 的和从 $\mathrm{10...}$ 开始的
然后你会发现就是你往上（就是到 $\mathrm{10...}$ 的）的是不会或到小于的值的，所以不会有多的。
然后另外一个自然就是会往上（因为或会让数变大，啊感性一下说变大），那因为你是连续的肯定要的 $01$ 都可以出现或不出现只要你有，所以你出现过 $1$ 的位都可以 $01$ 任选，就也是一个二次方。

然后发现少了，会发现第一个部分（最高位是 $0$）是可以融入到第二个部分里面的。
（因为你可以选 $\mathrm{10...0}$）使得变成第二部分的。

所以总的来说我们可以总结成若干个区间：
$[l,r]$
$[l+2^x,2^{x+1}]$（往上）
$[2^x,2^x+2^{y+1}]$（$y$ 是那个 $01$ 的位置的）
然后区间求并即可。

（妈的说的好抽象看代码得了）

代码

#include
#include
#define ll long long

using namespace std;

struct node {
	ll l, r;
}p[4];
ll L, R, a[66], b[66];

bool cmp(node x, node y) {
	if (x.l != y.l) return x.l < y.l;
	return x.r > y.r;
}

int main() {
	scanf("%lld %lld", &L, &R);
	for (int i = 0; i <= 60; i++) {
		a[i] = (L >> i) & 1; b[i] = (R >> i) & 1;
	}
	
	if (L == R) {printf("1"); return 0;}
	for (int i = 60; i >= 0; i--)
		if (a[i] != b[i]) {
			L ^= a[i] << i, R ^= b[i] << i;
			int pl = -1;
			for (int j = i - 1; j >= 0; j--) if (b[j]) {pl = j; break;}
			ll l1 = L, r1 = R ^ (1ll << i), l2 = (1ll << i) + L, r2 = (1ll << (i + 1)) - 1;
			ll l3 = (1ll << i), r3 = (1ll << i) + (1ll << (pl + 1)) - 1;
			p[1] = (node){l1, r1}; p[2] = (node){l2, r2}; p[3] = (node){l3, r3};
			sort(p + 1, p + 3 + 1, cmp);
			ll ans = 0; ll R = -1;
			for (int i = 1; i <= 3; i++) {//区间求交
				if (p[i].l > R) R = p[i].r, ans += p[i].r - p[i].l + 1;
					else if (p[i].r > R) ans += p[i].r - R, R = p[i].r;
			}
			printf("%lld", ans);
			return 0;
		}
		else L ^= a[i] << i, R ^= b[i] << i;
	
	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
38
39
40
41
42
43
44