Codeforces1058E 思维

Posted on | In , ,

给n个数，每个数的二进制位都可以调换位置，问满足区间[l,r] xor和为0的区间对数。
$(n\le 3·10^5, 1\le a_i\le 10^{18})$

题目链接

题解

  • 因为1的位置可以互相换，xor每次可以消掉2个1，故要满足区间二进制1的个数为偶数个并且二进制为1最多的一个数不能超过所有的一半
  • 问题转化为知道每个值的二进制位数和奇偶性，如何算对数
  • 因为$ 1\le a_i\le 10^{18}$，所以暴力算128位，剩下的直接算即可
  • 注意左端点要标注

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 3e5+7;
ll sum[maxn], a[maxn], summ[maxn], odd[maxn], even[maxn];
int n;
ll ans;

int main()
{
    scanf("%d", &n);
   // even[0]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld", &a[i]);
        int cnt=0;
        for(ll j=0;j<64;j++)
        {
            if((1LL<<j) & a[i])
                cnt++;
        }
        sum[i]=cnt;
    }

    ll ans=0, res=0;
    summ[0]=1;
    for(int i=1;i<=n;i++)
    {
        res+=sum[i];
        ans += summ[(res&1)];
        summ[(res&1)]++;
        ll maxx=-1 , s=0;
        for(int j=i;j>=max(1, i-128);j--)
        {
            s+=sum[j];
            maxx=max(maxx, sum[j]);
            if(s-maxx<maxx && s%2==0)
                ans--;
        }
    }
    printf("%lld\n", ans);
    return 0;
}