[TJOI2017]异或和

(ProblemLink)

题目大意

求序列所有连续和的异或值

Solution

考虑单独每一个二进制位(k)

设(S_i=sumlimits_{j=1}^ia[j],(S_0=0))

我们只需要知道(sumlimits_{i=1}^nsumlimits_{j=0}^{i-1}(S(i)-S(j))and (2^k))的奇偶性就可以知道答案中有没有k这一位

于是我们可以用权值树状数组统计,对于一个(i),前(i-1)个中有多少一个(j),(S(i)-S(j))在k这一位上是1

假如(S(i)and 2^k=1)

则答案就是在(k)这一位是0,且前(k)位小于(S(i))的(S(j))的个数加上在(k)这一位是(1),且前(k)位大于(S(i))的(S(j))的个数

(S(i)and 2^k=0)类似

于是用权值树状数组统计即可,注意下标(+1)

update:FFT也可以做诶

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
#define RG register
#define gi geti<int>()
#define gl geti<ll>()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>
IL T geti()
{
	RG T xi=0;
	RG char ch=gc;
	bool f=0;
	while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
	while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
	return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
	if(k<0)k=-k,putchar('-');
	if(k>=10)pi(k/10);
	putchar(k%10+'0');
	if(ch)putchar(ch);
}
const int N=1e6+7;
struct BIT{
	int c[N];
	vector<int>cur;
#define lowbit(x) ((x)&(-x))
	inline void add(int x,int addv){
		for(;x<=N;x+=lowbit(x))
		{
			if(!c[x])cur.push_back(x);
			c[x]+=addv;
		}
	}
	inline int query(int x){
		int ret=0;
		for(;x;x-=lowbit(x))ret+=c[x];
		return ret;
	}
	inline void clear(void)
	{
		for(auto i:cur)c[i]=0;
		cur.clear();
	}
}bit[2];
int s[N],ans,a[N];
int main(void)
{
	int n=gi,mx=0;
	for(int i=1;i<=n;++i)s[i]=s[i-1]+gi,chkmax(mx,s[i]);
	for(int i=0;i<=20;++i)
	{
		if(mx<(1<<i))break;
		bit[0].clear(),bit[1].clear();
		bit[0].add(1,1);
		for(int j=1;j<=n;++j)
		{
			int tmp=(s[j]>>i)&1;
			if((bit[!tmp].query(a[j]+1)+bit[tmp].query(N)-bit[tmp].query(a[j]+1))&1)ans^=1<<i;
			bit[tmp].add(a[j]+1,1);
			a[j]|=tmp*(1<<i);
		}
	}
	pi(ans);
	return 0;
}