题目

题意：

    给出一组序列，对于其中的元素可以任意改变其二进制下1的位置。求出区间[l,r]，使得这个区间的元素在操作后异或值为0。输出这样的区间数量。
$1≤n≤3⋅10^5，1≤a_i≤10^{18}$

分析：

    首先对于这种问题，一般都是枚举左区间，然后去计数右区间。
由于二进制位的数可以任意放置，所以我们只要考虑每个数1的个数就可以了。对于一个区间来说，当1的总个数大于最多1的那个数的两倍且总个数为偶数时，是符合条件的。因为我们总是可以用一个1消去最多的那个1，总数减2，最大值减1，仍保持两倍的状态。偶数自然是显然的，这样异或才能为1。
由于一个数的1的个数最多也就63位，所以当这个区间的总数超过其两倍时，第一个条件必然满足。那么我们只要保持1的个数为偶数即可。记当前的区间为[i,j]，那我们是去计[j+1,k]这个区间的1的个数与原区间1的个数相加为偶数的个数，即[j+1,n]这个区间内[j+1,k]的1的数量为偶数或奇数的个数。
因为1的数量具有累加性，所以我们可以先计算一个前缀和v[i]表示[1,i]区间1的数量，然后维护一个后缀和cnt[i]表示[i,n]这个区间v[j]为偶数的数量以便计数。那么当我们要算[j,k]区间1的数量，就可以用前缀和相减得到。由于我们只关注其奇偶性，所以若v[j]为偶数，则不影响，否则奇偶数量互换即可。

#include <iostream>
using namespace std;typedef long long ll; int num[300005],v[300005],cnt[300005];int count(ll x)
{int ans = 0;while( x ){if( x & 1 ) ans ++;x >>= 1;}return ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++){ll x;cin >> x;num[i] = count(x);}for (int i = 1; i <= n; i++){v[i] = v[i-1] + num[i];}for (int i = n; i >= 1; i--){cnt[i] = cnt[i+1];if( v[i] % 2 == 0 ) cnt[i] ++;}ll ans = 0;for (int i = 1; i <= n; i++){int sum = num[i];int maxn = num[i];for (int j = i + 1; j <= n; j++){sum += num[j];maxn = max(maxn,num[j]);if( sum % 2 == 0 && 2*maxn <= sum ) ans ++;if( sum > 128 ){if( sum % 2 == 0 ){if( v[j] % 2 == 0 ) ans += cnt[j+1];else ans += n - j - cnt[j+1];}else{if( v[j] % 2 == 0 ) ans += n - j - cnt[j+1];else ans += cnt[j+1];}break;}}}cout << ans << '\n';return 0;
}