Vasya有n个64位二进制正整数，小R有一种魔法，它可以让一个二进制数的任意两位交换，比如它可以将7(...000111)变成11(...001011)或者22(...010110),等等。对于一个序列，如果Vasya可以通过对任意多个序列中的数（可以是0个）使用任意多次（可以是0次）这种魔法，使得序列中的所有数异或和得0，则称这是一个好的序列。给定n个数a_1,a_2,a_3...a_n，问有多少对(l,r),1<=l<=r<=n,使得a_l,a_l+1,...,a_r是好的序列。

 

蠢了……没发现只有64个数可以直接枚举……

首先我们把每一个数字转化为它二进制数里$1$的个数，然后满足以下两点的是一个好的序列

1.区间和为偶数

2.区间内的最大数小于等于区间和的一半

第一个可以用前缀和优化到$O(n)$

然后第二个，我们可以从$i$开始往前枚举，因为最多只会有64个$1$，所以只要往前推64位来判断是否有不满足条件的就行了

1 //minamoto 2 #include
     
       3 #define ll long long 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template
      
       inline bool cmax(T&a,const T&b){
   return a
       
        =1&&j>=i-64;--j){32             while(k>j) cmax(mx,c[--k]);33             if(mx*2>sum[i]-sum[j-1]&&((sum[i]&1)==(sum[j-1]&1))) --ans;34         }35         ++cnt[sum[i]&1];36     }37     printf("%lld\n",ans);38     return 0;39 }