题解：AT_agc015_d [AGC015D] A or...or B Problem

· · 题解

思路一小时，

oo 不慎开太小，

调题三个钟。

——Garbage_fish 于 2024/11/13 21:41

神秘「找规律」做法。

Part 1 观察 2 的幂

0001 
0010 0011 
0100 0101 0110 0111 
1000

首先假设没有左边界研究一下，观察 4,8,16 这种 2 的幂，如上图所示。举 4 为例，你会发现和 4 一样位数的数，都可以通过 4 或上 4 以前的数得到，且这样或出来的数是不重不漏的。而和 4 一样位数的数之间，互相或也只能得到和 4 一样位数的数，因此可以只枚举 2 的幂。

0110 0111 
1000 1001 1010 1011 ... 1110 1111
10000

但现在有了左边界，假设是 6，如上图所示，你会发现通过 8 或 8 以前的数，只能取到 8\times 2-2 \sim 8\times 2-1，原因是 8-6=2，即当前枚举的次幂减去左边界（可以或上的数）。

这样子就会漏掉 8+1\sim 8\times 2-3 的所有数，但显然这个 3 可以算出来，加上这一部分的答案即可。

Part 2 处理左边

这种处理 2 的幂及其后面的做法，显然会漏掉左边界到左边界后面第一个 2 的幂中间的数，还是如上例，6\sim 7 就被漏掉了。

100100 100101 100110 100111
101000 101001 ... 101100 101101 101110 101111

观察第一行和省略号后面的数，会发现什么？(101000)_2 或上第一行的数可以得到省略号后面的数！两行的第一个数什么关系？加上 \operatorname{lowbit} 的关系！所以对于处理左边的，可以像处理 2 的幂的一样，从左区间开始不断增加 \operatorname{lowbit} 即可。

这是什么原理呢？加 \operatorname{lowbit} 相当于固定前面若干位，而后面几位显然又能构成“2 的幂”形式。

然后你会发现，对 2 的次幂乘 2，也是相当于加 \operatorname{lowbit}。由于这两部分更新答案原理一样，所以 Part 1 和 Part 2 只需一个循环即可搞定！

Part 3 处理右边

1000 1001 1010

如上例，询问的区间是 [8,10]，而 8 只能算出来它自己的一个答案，而 9，10 乃至 9 或 10 就被忽略了（显然 8+\operatorname{lowbit(8)}>10），怎么办？

可以把左边界移动到这个加上 \operatorname{lowbit} 就超出范围的 8 的后一位，对 [8+1,10] 进行和处理左区间相同的操作即可。

011
100 101 110 111

又会发现一个问题，如上例，询问的区间是 [3,7]，而 7 已经被 4 或上 3 算过了，计算区间 [5,7] 显然 7 又会被算若干次。所以对于「左边界移到 x 的后一位」操作，需要处理出 x 本来已经算到的地方 ed，这样子处理后面的东西时如果算到了 ed 就不要加上那一部分的。

然后就没了，实现的时间复杂度瓶颈是 \operatorname{lowbit}，可能略大于 O(\log (r-l))，「使用 4 个空格而不是制表符缩进」的代码仅 694\operatorname{B}（除注释）。

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int l, r;
int lowbit(int x) {
    return x & -x;
}
signed main() {
    IOS;
    cin >> l >> r;
    int i = l, ed = 9e18, ans = 0; // 初始 ed 要开 9e18，因为 1e18 < 2 ^ 60。
    for (; i <= r;) {
        if (i + i - l >= ed) // i 算的东西超过了 ed，已经被算过了。
            ans += max(0ll, ed - i);
        else // i 能算出哪些数？
            ans += i - l + 1;
        if (i + lowbit(i) > r) { // 移动左边界，并重新计算 ed。
            ed = (i + lowbit(i)) - (i - l);
            l = i = i + 1;
        } else {
            ans += max(0ll, min(r, (i + lowbit(i)) - (i - l) - 1) - i); // 有哪些被漏算了？
            i += lowbit(i);
        }
    }
    cout << ans << "\n";
    return 0;
}