codeforces 399 B.Code For 1配達規則

テーマリンク
http://codeforces.com/contest/768/problem/B
題意
一つの数x、0<=x==250をあげて、この数が1より大きい場合、この数をx/2、x%2、x/2のシーケンス（ここでの除算は整数除算）にして、シーケンスのすべての数が2より小さいまでこのシーケンスを続けます。その後、2つの数l、r、0<=r−l==105を与え、得られたシーケンス[l，r]区間の1の数はいくらですか？
考え方
このシーケンスは規則的であり、しかもこのシーケンスの長さはxの二乗の中で最小の数から1を減算します。シーケンスの中で1の個数はもちろんxです。直接コードをかけましょう。とても簡単に送ります。複雑度O（logn logn logs 50）。（cfである人がlowbitである人を確認しています。1の人かどうかは巧妙です。みんな自分でこの試合のスタンディングに行って上位のコードを見てください。）
コード

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int MAXN = 60;

LL bit[MAXN];
LL l, r;
LL n;

LL solve(LL pos, LL n) {
    LL len, ret = 0;
    while (pos > 0) {
        len = *upper_bound(bit, bit + MAXN, n) - 1;
        if (pos < (len + 1) / 2) {
            n /= 2;
        } else {
            ret += n / 2 + n % 2;
            pos -= (len + 1) / 2;
            n /= 2;
        }
    }
    return ret;
//    LL len = *upper_bound(bit, bit + MAXN, n) - 1;
//    if (pos == (len + 1) / 2) return n / 2 + n % 2;
//    else if (pos < (len + 1) / 2) return solve(pos, n / 2);
//    else return solve(pos - (len + 1) / 2, n / 2) + n / 2 + n % 2;
}

int main() {
    bit[0] = 1;
    for (int i = 1; i < MAXN; ++i) bit[i] = bit[i - 1] << 1;
//    for (int i = 0; i < MAXN; ++i) cout<while (~scanf("%I64d%I64d%I64d", &n, &l, &r)) {
        if (!n) {
            puts("0");
            continue;
        }
        printf("%I64d
", solve(r, n) - solve(l - 1, n));
    }
}