笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「水」CF768B Code For 1

posted on 2020-05-28 19:27:37 | under 题解 |

个人 vp 或者打休闲场的习惯都是先开 B 抢一血~~但是没抢 到过~~然后再做别的。发现这题没题解正好水个经验。

不难发现最后会构成一棵共有 $2^k$ 个节点的分治树,其中 $k=\lceil\log_2 n\rceil$ 。但是这其中有很多部分是重复的。随便画一下图可以发现对于区间内所有的奇数位置都会是一样的结果,取决于最后 $n$ 不断除以 $2$ 下取整是 $0$ 还是 $1$ 。而对于偶数位置则是某些 $n'\mod 2$ 。发现这些偶数位置的深度可能会有不同,同一深度结果相同。于是就可以预处理出每个深度的答案。最终复杂度 $O((r-l)\log n)$ 。


int cnt ;
int ans ;
int res1 ;
int hmf[N] ;
ll posv[N] ;
ll base[N] ;
ll n, l, r ;

int main(){
    cin >> n >> l >> r ;
    if (n == 1) return puts("1"), 0 ;
    ll m = n ; hmf[++ cnt] = m % 2 ;
    while (m / 2 > 1)
        m /= 2, hmf[++ cnt] = m % 2 ;
//    debug(hmf, 1, cnt) ;
    reverse(hmf + 1, hmf + cnt + 1) ;
    for (int i = 0 ; i <= 60 ; ++ i)
        posv[i] = 1ll << i ; res1 = m / 2 ;
    for (ll i = l ; i <= r ; ++ i){
        if (i & 1) ans += res1 ;
        else
            for (int j = cnt ; j ; -- j)
                if (i % posv[j] == 0) { ans += hmf[j] ; break ; }
//        debug(i, ' '), debug(ans) ;
    }
    cout << ans << '\n' ;
    return 0 ;
}