CF768B Code For 1 题解 分治

题目链接：http://codeforces.com/problemset/problem/768/B

解题思路：

分治。

本题和 的解题思路相似。

tips：如果如果 \(n\) 对应的区间完全被 \([l, r]\) 覆盖了，则区间 \([l, r]\) 范围内的所有数字和为 \(n\)。

示例程序：

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

#define int long long

int getlen(int a) {
    int res = 1;
    while (a) a >>= 1, res <<= 1;
    return res - 1;
}

int cal(int n, int l, int r) {
    if (l > r || r < 1) return 0;
    int m = getlen(n/2);
    if (l <= 1 && r >= m*2+1) return n;
    int res = cal(n/2, l, min(r, m)) + cal(n/2, max(1ll, l - m - 1), r - m - 1);
    if (l <= m+1 && m+1 <= r && n%2) res++;
    return res;
}

int n, l, r;

signed main() {
    cin >> n >> l >> r;
    cout << cal(n, l, r) << endl;
    return 0;
}