【HDU-5975】Aninteresting game【lowbit数列】

【HDU-5975】Aninteresting game【lowbit数列】

Solution:

对于查询1,我们可以发现,输出的其实就是L到R之间(包含L和R)所有数的lowbit之和,即\(\sum_{i = L}^Rlowbit(i)\)。但是我们不能去枚举这个数,因为枚举的平均复杂度是\(O(n)\),而这道题的n取值为1e18.我们采用前缀和的方法,因为我们可以\(O(logn)\)的时间复杂度求出从1到n之间的所有数lowbit之和,我们先考虑如果对于单个要求的lowbit,如何求出拥有这个lowbit的数在1到x中出现的次数,如果我们用x除以\(lowbit(i) = 2^k\),就可以知道x中有多少个不小于\(2^k\)的数,用它再减去x中有多少个不小于\(2^{k + 1}\)的个数,就得知了拥有lowbit(i)的数的个数,由于我们要求它们lowbit之和,求出每个拥有lowbit(i)的数的个数,再乘上lowbit(i)就可以了,于是我们的策略就是枚举lowbit(i)。【这道题时间卡很紧,这个查询尽量避免多余的移位、乘除、条件判断操作,否则会超时】

对于查询2,直接把平常树状数组更新操作的循环那里加一个计数,即可解决。

#include <iostream>

using namespace std;

typedef long long LL;

LL query1(LL x) {
    LL ret = 0;
    for (LL i = 1; i <= x; i <<= 1) {
        ret += ((x / i) - (x / (i << 1))) * i;
    }
    return ret;
}

LL query2(LL x, LL n) {
    LL ret = 0;
    while (x <= n) {
        x += x & (-x);
        ret++;
    }
    return ret;
}

int main(void) {
    LL n, q, l, r;
    int op;
    while (~scanf("%lld%lld", &n, &q)) {
        while (q--) {
            scanf("%d", &op);
            if (op & 1) {
                scanf("%lld%lld", &l, &r);
                printf("%lld\n", query1(r) - query1(l - 1));
            } else {
                scanf("%lld", &l);
                printf("%lld\n", query2(l, n));
            }
        }
    }
    return 0;
}

相关阅读:

关于这个数列与此数列的前缀和:

lowbit数列:https://oeis.org/A006519

lowbit数列前缀和:https://oeis.org/A006520