codeforces 1041 E.Vasya and Good Sequences(暴力？)

3
6 7 14

2

4
1 2 1 16

4

对于任何一个$$$a_i$$$，可以将其表示为$$$2$$$进制并任意更改它里面1的位置。对于区间[l,r]，如果对其中一些数执行任意次这样的操作，从而使得区间的异或和为0，就称这段区间是good。给$$$n$$$个数，$$$1\le a_i\le 10^{18}$$$，求有多少个子区间是good。

异或和只与二进制中$$$1$$$的个数有关，所以用$$$b_i$$$记录$$$(a_i)_2$$$中的$$$1$$$的个数，形成一个新的数组$$$b[n]$$$，之后就不再考虑数组$$$a[n]$$$了。
为了方便叙述，用$$$x\oplus y$$$表示对$$$x,y$$$进行任意调整后，可能的异或值的集合。容易发现两个数的情况($$$x\lt y$$$)，结果是一个公差为2的等差序列: $$$$$$ \begin{align} x\oplus y=\{|y-x|,\ |y-x|+2,\ ...,\ x+y \} \end{align} $$$$$$ 三个数的情况($$$x\lt y\lt z$$$)，结果也是公差为2的等差序列： $$$$$$ \begin{align} x\oplus y\oplus z=\{min\{|z-t|,\ t\in x\oplus y\},\ ...,\ x+y+z \} \end{align} $$$$$$ 分析可以发现，区间可能的异或值的范围，上限是区间和，下限是一个小于最大元素的数，要判断异或值能否为0，最暴力的方法，就是把$$$min\{...\}$$$里面遍历一遍，看0是不是在其中，而这需要很大的代价。
有一个更好的解决办法，注意到上限是一个很容易维护的值，而下限一定小于区间的最大元素，假设$$$[l,r]$$$内最大和第二大的数分别为$$$b_i,\ b_j$$$，把$$$b_i$$$单独拿出来，剩下的数形成新的区间，那么新区间的上限就是的新的区间和，下限就是一个小于$$$b_j$$$的数，所以下限一定小于$$$b_i$$$。要让原区间下限为0，就转而去判断新区间对应的等差序列中有没有$$$b_i$$$，因为如果有，就可以抵消掉，从而原区间的下限就是0。具体的来说，$$$b_i$$$要在其中，要满足两个条件：
【1】上限大于或等于$$$b_i$$$；
【2】$$$b_i$$$与上限同奇偶；
这样一来，通过上限就能确定区间是否为good，完全避免了对下限的考虑了。但是单独把$$$b_i$$$提出来还是很麻烦，不如把条件转化为对整个区间的限制：
【1】区间和大于或等于最大元素的两倍；
【2】区间和是偶数；
还有一个性质，$$$b_i$$$的范围是1~63，也就意味着，只要区间的长度不小于64，区间和≥63+$$$b_i$$$≥$$$2b_i$$$，就一定满足条件【1】，所以只用考虑所有长度小于64的区间，于是问题的规模就缩小到了64n，就变成了一个使劲码就能做出来的题了。
一种比较好的写法是，先算求和为偶数的区间的总个数，再遍历所有长度小于64且和为偶数的区间，从总个数中去掉不满足条件的，剩下的个数就是答案。

分析问题眼光还是不够敏锐啊。结合了官方题解+拜读大佬的代码，整理出这样一个还算完整的思路，花了一晚上。什么时候才能在比赛中，独立做出这样的题呢。

#include<stdio.h>
typedef long long LL;
int cnt(LL x) {
    int res = 0;
    while (x)res += x & 1, x >>=1;
    return res;
}
int b[300005]={0},fre[300005]; 
LL ai;
int cnt0 = 0, cnt1 = 0;
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;++i)    {
        scanf("%I64d", &ai); b[i] = cnt(ai); fre[i] = fre[i - 1] + b[i];
        if (fre[i] & 1)cnt1++;
        else cnt0++;
    }
    /*求和为偶数的区间个数：
     *
     *对于前缀和为奇数的[0,l1], [0,l2], ..., [0,lcnt1]
     * 对l1而言，它和后面的组合起来，[l1+1,l2], [l1+1,l3], ..., [l1+1,lcnt1]的和一定全都是偶数
     * l2~lcnt1也同理，共cnt1-1+cnt1-2+...1=cnt1(cnt1-1)/2个
     * 
     * 对于和为偶数的区间[0,r1], [0, r2], ..., [0,rcnt0]
     * 
     * 不仅和奇数的相同，每个区间本身也要加入计数
     * 所以共cnt0+cnt0-1+...+1=(cnt0+1)cnt0/2个
     */
    LL ans = 1LL * cnt1*(cnt1 - 1) / 2+1LL*cnt0*(cnt0+1)/2;

    //遍历所有以i为起点的区间
    for(int i=1;i<=n;++i)    {
        int maxn = 0,sum;
        //只检查到长度为64
        for(int j=0;j<=64&&i+j<=n;++j){
            if (maxn < b[i + j])maxn = b[i + j];
            sum = fre[i + j] - fre[i - 1];
            if ((sum & 1) == 0 && (maxn<<1) > sum)ans--;
        }
    }
    printf("%I64d", ans);
}