关键词:二进制
相关题目:$CF1058E$

题意

给定$n(n\leq 300000)$个数,值域 $1 \sim 1e18$
定义操作为,将一个数转换成二进制后,可以将其变为任何与其1个数相同的数(位数不限)

求区间 $(l,r)$ 使区间内的数经任意操作后异或和为0的区间数

Solution

首先发现数的具体值对答案没有影响,所以先把数处理成1的个数

易得
1.一个区间内1个数和为偶数
2.且1的个数的最大值不大于1个数和的话

这个区间就是合法的

首先考虑如果只有第一个条件怎么办
维护三个前缀和:1的个数和,前缀和为奇数的个数和,前缀和为偶数的个数和

然后枚举一下左端点,用三个前缀和算一下当前左端点对答案的贡献就好了

等等?!似乎还有个条件2??

冷静分析

发现一个数1的个数最大只有63个,最少也有1个
似乎只要区间长度大于64,第二个条件就一定满足?
对于每一个左端点向右枚举一下右端点,单独算一下
直到区间长度大于64再用前面所说的前缀和算一下剩下的贡献就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
const int N=300100;
using namespace std;
int n,a[N],sum[N],f[10][N];
long long ans,x;
int main(int argc, char const *argv[]){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&x);
while(x) a[i]+=x&1,x>>=1;
}
for(int i=1;i<=n;i++) {
sum[i]=sum[i-1]+a[i];
f[sum[i]&1][i]=1;
}
for(int i=1;i<=n;i++){
f[0][i]+=f[0][i-1];
f[1][i]+=f[1][i-1];
}
for(int l=1,r,maxn;l<=n;l++){
maxn=a[l];
for(r=l+1;r<=n&&r-l+1<=64;r++){
maxn=max(a[r],maxn);
if((sum[r]-sum[l-1])%2==0&&maxn*2<=(sum[r]-sum[l-1])) ans++;
}
ans+=f[sum[l-1]&1][n]-f[sum[l-1]&1][r-1];
}
printf("%lld\n",ans);
return 0;
}