XOR Problem
题目分析
求区间异或和的与的最大权值。看到区间异或和的时候，我们总会熟练的先进行区间前缀异或和，然后将区间两端的前缀异或和异或就可以得到区间异或和，不理解的可以先做一些01字典树的问题。那么我们的问题就变成了\(f_x=a_1 \oplus a_2 \oplus ⋯ \oplus a_x\)求\(w_1,w_2,w_3,⋯,w_m\)得到\(g_i=f_{w_i}\oplus f_{w_{i-1}}\)
使得\(g_1\mid g_2 \mid ⋯\mid g_m\)最大。
然后考虑最大权值，我们容易想到我们可以通过从高位到低位，将可行的位置赋1就可以了。那么，我们可以从高位到低位枚举，如果这个位置填1满足条件，且满足之前填的1，则这个位置填1。因为高位填的1一定要算在答案中，所以这样就可以得到最大值。
现在，我们考虑每个位置的1所需要满足的条件是什么。
首先我们如果要满足这个位置的区间与的1，则这个区间所有值都得是1，也就可以得出\(f\)异或时在这个数位必须是01交错排列的，而\(f_{w_1}\)异或的是0，就可以将0看做是\(f_{w_0}\)所以我们有\(f_{w_{2i}}\)在这位是0，\(f_{w_{2i+1}}\)在这位是1。
int l=ans|(1<<k),cnt=1;//cnt指可行的异或区间个数，但因为第0位是偶数，而f[0]其实是第1个区间，所以区间个数为偶数时实际是第奇数个f[i]，因此我们在这里将它+1，后面再减回
for(int i=1;i<=n;i++)
{if((((f[i]&l)==0&&(cnt%2==1))||((f[i]&l)==l)&&(cnt%2==0)))cnt++;//在l为1的地方第偶数个f[i]必须都为0，第奇数个f[i]必须都为1
}
其次，题目的限制是我们必须划出m个区间，因此我们可划区间的个数一定要大于等于m。
if(cnt-1>=m)return 1;
else return 0;
然后我们的\(w_m=n\)，所以首先必须满足\(f_n\)满足条件。即如果\(m\)是偶数，则\(f_n\)在这位是0，因此\(f_n\)的数位必须在答案的数位为1的地方为0。反之，如果\(m\)是奇数，则\(f_n\)在这位是1，因此\(f_n\)的数位必须在答案的数位为1的地方为1。
if(!((m%2==0&&(l&f[n])==0)||(m%2==1&&(l&f[n])==l)))return 0;//m为偶数时，在l为1的地方f[n]必须为0。m为奇数时，在l为1的地方f[n]必须为1
最后再从\(\log(n)\)枚举每个\(k\)看在第\(k\)位能否填1，就能得出答案了。