题目链接：

https://www.lydsy.com/JudgeOnline/problem.php?id=4017

第一问

$xo\left[i\right]$xo[i]表示前 $i$i个数的异或值， $sum\left[i\right]$sum[i]表示前 $i$i个数的和
第一问：用 $cnt\left[k\right]\left[0\right]，cnt\left[k\right]\left[1\right]$cnt[k][0]，cnt[k][1]表示第 $k$k位 $0$0的个数和 $1$1的个数，朴素的做法是枚举 $L$L和 $R$R要 $O\left(n^2\right)$O(n2)
我们先枚举 $R$R，如果 $sum\left[R\right]$sum[R]的第 $k$k位是 $1$1，要是有个 $sum[L-1]$sum[L−1]的第 $k$k位是 $0$0就好啦~，那我们的这个 $sum\left[LR\right]$sum[L R]区间的第 $k$k位就是 $1$1了，我们要做的就是统计出每枚举的一个 $sum\left[R\right]$sum[R]有多少个 $sum[L-1]$sum[L−1]与他异或是 $1$1的，而且不需要知道具体是哪几个 $L$L，只需要知道有多少个，那么个数就是 $cnt$cnt里面保存的，是 $1$1就找 $0$0，是 $0$0就找 $1$1。

第二问

第二问其实就是bzoj 4888
这道题拖了好久，再学姐的帮助下终于过了T_T
bzoj 4888 题解
然后就是因为只用判断奇偶，所以就把树状数组优化成异或的形式了，很多大佬的博客都是这么写的，但是我还是比较喜欢比较有原始意义滴~所以就没有改成异或的那种

这道题的数据范围差不多是1e5*1e6=1e11，所以要用long long ，移位的时候注意用1LL
T_T

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int MOD=998244353;
int xo[maxn],a[maxn];
int tree[maxn];
LL sum[maxn],P[maxn];
int N,n;
LL Cnt[25][2];//极限数据1e5再左移20位就爆int了 
LL solve1()
{
    LL res=0;
    memset(Cnt,0,sizeof(Cnt));
    for(int k=0;k<=20;k++)
    {
        for(int r=1;r<=N;r++)
        {
            int t=1&(xo[r]>>k);
            if(t==1)res+=1<<k;//相当于就他一个数这个区间
            Cnt[k][t]++;
            res+=Cnt[k][t^1]<<k;
            res%=MOD;
        }
    }
    return res;
}
void Add(int pos)
{
	if(pos<0)return ;//有-1，所以要提前退出 
	pos++;//因为有0这个位置，所以树状数组的都加1
	for(int i=pos; i<maxn; i+=i&-i)tree[i]++;;
}
int getsum(int pos)
{
	pos++;
	int res=0;
	for(int i=pos; i>0; i-=i&-i)res+=tree[i];
	return res;
}
int idx(LL x)//找最后一个小于等于他的数，所以是upper_bound-1
{
	return upper_bound(P,P+n+1,x)-P-1;//注意，还有减1
}
LL solve2()
{
	LL res=0;
	for(int k=0; k<=40; k++)//差不多1e11，所以40位就差不多了 
	{
		memset(tree,0,sizeof tree);
		LL tp=0;
		for(int i=1;i<=N;i++)P[i]=sum[i]%(1LL<<(1+k));
		sort(P,P+1+N);
		//unique这里弄出来是有n+1个数，但是我想把P[n]作为最后一个数，因此，还减了一个1
		n=unique(P,P+1+N)-P-1;
		for(int i=0;i<=N;i++)//这里要从0开始，我也不是很懂为什么
		{
			LL now=sum[i]%(1LL<<(k+1));
			Add(idx(now));
			tp+=getsum(idx(now-(1LL<<k)));//第一个不等式
			tp+=getsum(idx(now+(1LL<<k)))-getsum(idx(now));//第二个不等式，求夹在中间的那一坨
		}
		if(tp&1LL)res|=(1LL<<k);
	}
	return res;
}
int main()
{
    while(cin>>N)
    {
        for(int i=1;i<=N;i++)
        {
            scanf("%d",a+i);
            sum[i]=sum[i-1]+a[i];
            xo[i]=xo[i-1]^a[i];
        }
        cout<<solve1()<<" "<<solve2()<<endl;
    }
}