题解：CF2152D Division Versus Addition
20090818Cc
·
·
题解
题意：
定义一个序列的价值为二人博弈的回合数，给定序列 a。
然后 q 次询问 a 序列区间 [l,r] 的价值。
博弈过程：
A ，B 轮流对序列操作：
- A 每次将序列中一个数 x 除二。
- B 每次将序列中一个数 x 加一。
其中 x≠1。\
当序列中所有数都是 1 时，结束博弈。
A 希望操作次数越少越好，B 希望操作次数越多越好。
分析：
首先将数放到二进制上看，发现实际上是每次将一个数 x 右移一位，所以基础的移动次数就是 \log_2(x)：
-
考虑 B 怎么操作才能让操作次数增加？
一种很显然的办法就是让 x 的二进制进位，就会增加一次。
显然的是会让 4 次变成 5 次。
所以当二进制全部为 1 时，B 就会操作一次让总次数 +1 。
-
那些数满足会让操作次数 +1 呢？
所以不是 2 的整数次幂的数都会让操作次数 +1 。
比如一个数中间有 1 时：
-
当数是 2 的整数幂时，A 可以跟随 B，每次 B + 1 后，A 就右移一位消去新增的 1 ，次数不变。
-
博弈何在？
结论，A B 会争夺 x=2^k+1 这样的数。A 先动操作次数不变，B 先动操作次数 +1 。
所以 A，B会优先变化这样的数，每人操作一半。
-
那么思路就很明白了，记录三种数的个数，令区间内非 2 整数幂的数个数为 |C|，为 x=2^k+1 的数个数为 |B|，区间原来所以二进制位数和为 sum。
那么可得出答案式子：
## 代码：
使用前缀和维护即可。
```
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define INF 1e18
#define lb long double
#define ls (id<<1)
#define rs (id<<1|1)
#define rep(i,l,r,k) for(int i=(l);i<=(r);i+=(k))
#define dep(i,r,l,k) for(int i=(r);i>=(l);i-=(k))
#define mk(a,b) make_pair(a,b)
#define me(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define pr putchar
#define fi first
#define se second
#define max(a,b)((a)>(b)?(a):(b))
#define min(a,b)((a)<(b)?(a):(b))
using namespace std;
random_device rd;
unsigned int seed=rd();
mt19937 Rand(seed);
typedef pair<int,int> pii;
const int M=3e5+110,mod=1e9+7,Mod=998244353;
__gnu_pbds::gp_hash_table<string,int>ml;
inline int read(){int sum=0,k=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();
}while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
}return sum*k;
}inline void wr(int x){if(x<0) putchar('-'),x=-x;
if(x>9) wr(x/10);return void(putchar(x%10+'0'));}
int T=read(),n,m,b[M],c[M],he[M];
inline int pan(int x){
//lowbit判断是否为2的正整数次幂
if(x==(x&-x)) return 1;
x--;//减去一判断是否为2的正整数次幂
if(x==(x&-x)) return 2; // 为B类数
return 3;// 为C类数
}
signed main(){
while(T--){
n=read(),m=read();
rep(i,1,n,1){
int x=read(),op=pan(x);
b[i]=c[i]=he[i]=0; // 初始化
if(op==2) b[i]++;
if(op==3) c[i]++;
// 维护前缀和
he[i]=he[i-1]+(int)log2(x);
b[i]+=b[i-1];c[i]+=c[i-1];
}
while(m--){
int l=read(),r=read();
cout<< // 如题解
he[r]-he[l-1]+
c[r]-c[l-1]+
(b[r]-b[l-1])/2
<<'\n';
}
}
return 0;
}
```