本文主要是介绍Sum of xor sum UVALive - 8518 —— 求区间所有子区间异或和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
给你一些数，每次问你从l到r这个区间的所有子区间异或和是多少。
题解：
这种题目总是会把自己绕进去啊，看了别人的题解发现和自己想的差不多，但是自己还是没有想出来。
这种题目的话一般就是看每个数的每一位的贡献，这一位只有在奇数个区间内才有贡献。那么对于这一道题目来说，答案的计算方法可能是sum[r]-sum[l]-（左区间对右区间的影响）。
那么为了求出sum数组，需要知道到达当前位的时候有多少个奇数区间，这时候候用异或前缀和就会方便很多用zero[i]表示到第i位的时候异或前缀和有过多少个0，one表示有过多少个1，这样的话当新到达的位置的异或前缀和是0的时候，那么就表示有偶数个1，那我们只需要-one[i-1]，就表示将其分为两个奇数个1的区间的数量。由于在0位置的时候就是0，那么zero一开始需要置为1，否则之后就会少一个到0为止的区间。
左区间对右区间的影响就是左端点在左区间，右端点在右区间且其中的1的个数是奇数的情况。这时候我们不需要知道pre[l-1],pre[r]是否是1，我们只需要让左端点-1的位置到右端点的位置中间的1是奇数的即可，所以只需要一个用one，一个用zero，那么相减之后就是答案。为什么是l-2，因为左端点要<=l-1，如果是l-1的话就表示从l开始了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=1e5+5;
int pre[N][21],one[N][21],zero[N][21],a[N];
ll sum[N][21];
int main()
{int t;for(int i=0;i<=20;i++)zero[0][i]=1;while(~scanf("%d",&t)){while(t--){int n,q;scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);for(ll j=0;j<=20;j++){pre[i][j]=pre[i-1][j]^(a[i]&(1<<j)?1:0);one[i][j]=one[i-1][j]+pre[i][j];zero[i][j]=zero[i-1][j]+(pre[i][j]?0:1);if(!pre[i][j])sum[i][j]=(sum[i-1][j]+one[i-1][j]*(1<<j))%mod;elsesum[i][j]=(sum[i-1][j]+zero[i-1][j]*(1<<j))%mod;}}while(q--){int l,r;scanf("%d%d",&l,&r);ll ans=0;for(int i=0;i<=20;i++){ans=(ans+sum[r][i]-sum[l-1][i]+mod)%mod;if(l>2)ans=(ans-zero[l-2][i]*(one[r][i]-one[l-1][i])*(1ll<<i)%mod-one[l-2][i]*(zero[r][i]-zero[l-1][i])*(1ll<<i)%mod)%mod;ans=(ans+mod)%mod;}printf("%lld\n",ans);}}}return 0;
}这篇关于Sum of xor sum UVALive - 8518 —— 求区间所有子区间异或和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
