题解 | #计算几何#

简单的说一下思路

首先对于右边界r，为了计算 0 到 r（闭区间）内有多少个数的二进制包含奇数个1，我们对右边界的二进制格式进行处理。
比如这里我们有一个数的二进制格式为 （一共64位，考虑到题目给定 r 的最大值是 ），我们从高位往低位遍历，每当我们碰到了一个1，比如上面这个数最左边第一个1，我们需要考虑的是从 到 之间一共有多少个数的二进制包含奇数个1，问题变成这样就很简单了。一共有5位需要考虑，想让这5位里包含奇数个1，总共有 种01序列，也就是 种。接下来我们碰到第二个1，需要考虑的范围是 到 ，想让最后3位包含偶数个1（因为前面已经有了奇数个1），一共有 种01序列，也是 。这样做下去我们就能考虑到从 到 之间的所有情况。

只要能算出来 0 到 r 里有多少个数的二进制包含奇数个1。我们用同样的办法算出 0 到 l-1 里有多少个数，就能很容易的得出从 l 到 r 里有多少个我们需要的数了。

代码如下

#include <bits/stdc++.h>
#include <bitset>
using namespace std;

long long cntt(long long d){
    bitset<64> x(d);

    long long ans = 0;
    int cnt = 0;
    for(int i = 63; i > 0; --i){
        if(x[i] == 1){
            cnt++;
            ans += pow(2, i-1);
        }
    }

    // 对最低位需要做一些特殊处理
    if(cnt%2 == 1)
        ++ans;

    if(x[0] == 1){
        cnt++;
        if(cnt%2 == 1)
            ++ans;
    }

    return ans;
}

int main(){
    int T;
    cin >> T;
    vector<long long> ans;

    for(int k = 0; k < T; ++k){
        long long l, r;
        cin >> l >> r;

        ans.push_back(cntt(r)-cntt(l-1));
    }

    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;

    return 0;
}