「水」CF768B Code For 1
皎月半洒花
2020-05-28 19:27:37
个人 vp 或者打休闲场的习惯都是先开 B 抢一血~~但是没抢
到过~~然后再做别的。发现这题没题解正好水个经验。
不难发现最后会构成一棵共有 $2^k$ 个节点的分治树,其中 $k=\lceil\log_2 n\rceil$ 。但是这其中有很多部分是重复的。随便画一下图可以发现对于区间内所有的奇数位置都会是一样的结果,取决于最后 $n$ 不断除以 $2$ 下取整是 $0$ 还是 $1$ 。而对于偶数位置则是某些 $n'\mod 2$ 。发现这些偶数位置的深度可能会有不同,同一深度结果相同。于是就可以预处理出每个深度的答案。最终复杂度 $O((r-l)\log n)$ 。
```cpp
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 ;
}
```