CWOI S C0327 B 或 | EarthMessenger 博客

题意

U2FsdGVkX1+D4A6QfCouIQBuNbTwssLV3uusFcpmbnb5RSEe4lLnhIgliMrCJZQP
or6+uBxEqSKqU8YRPzzrIEs/knK5/Y/T/Mdp9BGdq37PaMf80RJBtza1waVZv2uf
s7kALpfRDqlLO9umT0DGFbsUW492vwDb0rcPXrAceN6tNYacsBv0+Uk61mlo+7ng

解析

假设 L 和 R 的二进制表示中，有共同的一段前缀，则可以把这段前缀忽略掉，因为不管怎么取，这段前缀的值都是一样的。为了方便，不妨把这段相同前缀全部变成 0。

假设 L 和 R 最高的不同位为 k，即 L 的第 k 位为 0 且 R 的第 k 位为 1，且比 k 更高的位全部为 0。我们分别考虑一下几段对答案的贡献：

$[L, 2^{k}-1]$ ：这一段能表示出来的值显然是 $[L, 2^{k}-1]$ 。
$[2^{k}, R]$ ：下界显然是 $2^{k}$ ，因为任意两个正整数或起来一定不小于原来那两个正整数。对于上界，假设 R 第二高的为 1 的位是 p，那么 p 以下的所有位都可以任意取，就是 $2^{k}+2^{p+1}-1$ 。如果 $R=2^{k}$ ，即没有第二高的为 1 位，可以在实现的时候把 p 当作 -1，式子仍然成立。所以能表示出来的值是 $[2^{k}, 2^{k} +2^{p+1}-1]$ 。
以上两个组合到一起：把 $2^{k}$ 和第一个区间里每个数组合，可以得到： $[2^{k} +2^{k+1}-1]$ 。

把这三段区间求并即可。

实现

int main()
{
	u64 l, r;
	std::cin >> l >> r;

	if (l == r) {
		std::cout << 1 << std::endl;
		return 0;
	}

	int k = 63;
	while (k >= 0) {
		if (((l >> k) & 1) != ((r >> k) & 1)) break;
		l &= (-1ull) ^ (1ull << k);
		r &= (-1ull) ^ (1ull << k);
		k--;
	}

	int p = k - 1;
	while (p >= 0) {
		if ((r >> p) & 1) break;
		p--;
	}

	u64 ans = (1ull << (k + 1)) - l;
	if (l > (1ull << (p + 1))) ans -= l - (1ull << (p + 1));
	std::cout << ans << std::endl;
}