zcmimi's blog

arrow_back拆位共1篇文章

avatar
zc
2020-10-28 15:23:37

查看原题

点击跳转

难点在于第二问

第一问:

二进制拆位后分别统计就可以了

第二问:

枚举每一位,统计答案该位是否为1

设序列前缀和为S

区间[l,r]区间和二进制下第k位为1,那么(S_r-S_{l-1}) \mod 2^{k+1}\ge 2^k

S_{l-1} \mod 2^{k+1} \le (S_r \mod 2^{k+1})-2^kS_{l-1}\ge 0

S_{l-1} \mod 2^{k+1} \le (S_r\mod 2^{k+1})+2^kS_r<S_{l-1}

离散化后树状数组即可统计

1/1
Search
search