题解：CF2152D Division Versus Addition

· · 题解

博弈论太可爱了，贴贴 /se

如果没有增加的情况，那么答案显然就是 \log a_i 吧。

然后你发现对于一个偶数的增加实质上是无用功，只要立马除去那么就没有任何影响。

如果在不断的除法中出现了奇数且不是 1，那么我从现在开始不停地往这个数字上面堆加法，最后位数削减的速度一定没有我这个 1 左移的快。

于是这样就会多一次贡献。

所以你会发现 2 的幂次是不可能有这个机会的，其他数字都可以。

但是到此为止了吗？有个特例。

如果是 2^k+1 这样的数，转成二进制就是 \texttt{100\dots001}，那么如果是除法先施放上去则不产生贡献，如果是加法则反之。

这是一个需要争抢的资源，显然只有一半可用，单拎出来统计答案。

于是做两个前缀和就做完了。

#include<bits/stdc++.h>
#define mk make_pair
#define pb push_back
#define mod 998244353
#define int long long
using namespace std;
int sum[250005];
int sum2[250005];
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        int flc=x,kel=1;
        int cnt=0;
        while(flc)cnt++,flc>>=1;
        kel<<=cnt-1;
        sum[i]=sum[i-1]+cnt-(x-kel<=1);
        sum2[i]=sum2[i-1]+(x-kel==1);
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]+(sum2[r]-sum2[l-1])/2<<'\n';
    }
}
signed main(){
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 莫妮卡只感到强烈的困惑。
// 恐怕世人做梦也万万想不到，从前威震利迪尔王国的沃岗黑龙，竟然与乌鸦展开惨绝人寰的死斗吧。