4725: 【GESP2509五级】有趣的数字和

#include <algorithm>
#include <cstdio>
using namespace std;
int l, r;
long long ans;
pair<int, long long> cal2(int n, int p) {
    if (n == 0) { return {1 - p, 0}; }
    if (n == 1) { return {1, p}; }
    return {(n + 1) / 2, 1ll * n * (n + 1) / 4};
  
}
pair<int, long long> cal(int n, int p) {
    if (n <= 1) { return cal2(n, p); }
    long long x = 1ll << (31 - __builtin_clz(n));
    auto l = cal2(x - 1, p);
    auto r = cal(n - x, 1 - p);
    return {l.first + r.first, l.second + r.second + x * r.first};
}
int main() {
    scanf("%d%d", &l, &r);
    ans -= cal(l - 1, 1).second;
    ans += cal(r, 1).second;
    printf("%lld\n", ans);
    return 0;
}