【Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined) B】 Code For 1

在这里输入题意

【题解】

把序列生成的过程看成一颗树
会发现最后形成的是一颗二叉树。
每个二叉树上的节点就对应了序列中的一个数字。

如果我们把每个节点都往下投影的话。

(而且整棵树都是左右对称的。那么每个子树的根节点就是(l+r)/2了

就像是整个序列了。

(中序遍历

则我们可以用线段树求区间和的方法。

现在相当于告诉你1..n这个区间。

然后你要求l..r这个区间的和。

递归求就好。

【代码】

#include <bits/stdc++.h>

#define LL long long

using namespace std;

LL n,l,r;

LL dfs(LL n,LL L,LL R,LL l,LL r){

    LL mid = (l+r)>>1;

    LL temp = 0;

    if (l==r) return n;

    if (L<mid) temp+=dfs(n/2,L,R,l,mid-1);

    if (mid<R) temp+=dfs(n/2,L,R,mid+1,r);

    if(L<=mid && mid<=R) temp+=n%2;

    return temp;

}

int main()

{

    cin >> n >> l >> r;

    LL tot = 1,x = n;

    while (x>1){

        tot = tot + 1 + tot;

        x>>=1;

    }

    cout<<dfs(n,l,r,1,tot)<<endl;

    return 0;

}

巴特西

【Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined) B】 Code For 1

最新文章

热门文章