题意如果一个序列中[l,r]里面的数，可以通过调整每个数的二进制位使得其异或和为0，那么这个[l,r]对就是good的，然后求有多少个这种[l,r]对，序列长度3e5。
一开始想dp，又是分位又是奇偶的，始终没搞出来。看了官方题解才发现判定一个[l,r]段是否为goog的充分必要条件只有两个，首先设bi为ai的二进制表示中的1的个数，则充要条件为：
① Σbi(l<=i<=r) 为偶数
② max(bi)<=Σbi(i!=index(max(bi))
第一个条件很容易理解：每次异或消掉的一定是一对1，如果最后能全消掉那么一定是偶数个1。第二个条件，一群数字异或之后能得到的最多1的数量是 min(他们的和,64)，这是因为可以任意摆布每个数字里每个1的位置。然后要消掉某个数，那一定得其他数字能达到的最多1起码不小于这个数字的1个数，然后我们发现只要拥有最多1的数字满足这个限制，那剩下的一定满足这个限制（剩下的bi肯定比最大的小，而“其他的和”一定又比之前的大，所以最大的满足的话其他一定满足。
但是这样的话，假使使用遍历左端点然后求右端点个数的策略，需要同时考虑两个条件就会使得复杂度为O(n²)，但是注意到每一个数字最少有一个1(1<=ai），那么当段的长度大于64（实际61就够了）的时候，最大的那个数字的1的数量一定小于其他所有数bi的和，因为最大的那个再大也大不过64，其他的和由于每个至少为1所以至少不小于64，所以第二个条件这时候是肯定满足的。这也就意味着我们可以暴力判别长度为64范围内的不合法得情况。
再来看第一个条件，其实可以预处理出来一个后缀和cnt[2][i]，表示从当前i位置往后算，有多少个端点加到n的bi和为奇数/偶数，这样的话，只要根据当前的bi是奇数还是偶数选择加哪个就可以了。
实现时需要注意的细节是，由于cnt这个东西保存的某种意义上是左闭区间，所以从后往前算当前一点的时候只能算cnt[i+1]的，这个地方wa了。然后也是由于这个性质，需要给cnt[0][n+1]赋值为1.（如果不这样就会出现明明为偶数却什么都没加的情况）
#include#include #include #include