bzoj 4017 小Q的无敌异或

Posted on | Edited on | Views:

树状数组.

对于第一问,将每个二进制位分开计算贡献,变为 $0/1$ 数列,询问有几个区间的异或和为 $1$ ,随便做做.

对于第二问,仍然将每个二进制位分开算,只需要考虑所有的区间和的第 $i$ 位有奇数个 $1$ 还是偶数个 $1$ .

记前缀和 $sum(x)=\sum_{i=1}^x a_i​$ ,那么每个区间和都是 $sum(r)-sum(l-1)​$ 的形式.

从前往后枚举 $r$ ,若 $sum(r)-sum(l-1)$ 第 $i$ 位上为 $1$ ,则只有两种可能.

一种是 $sum(r)$ 与 $sum(l-1)$ 第 $i$ 位不同,且 $sum(r)\bmod 2^i\ge sum(l-1)\bmod 2^i$ ,即没有向第 $i$ 位借位.

另一种是 $sum(r)$ 与 $sum(l-1)$ 第 $i$ 位相同,且 $sum(r)\bmod 2^i< sum(l-1)\bmod 2^i$ ,即有向第 $i$ 位借位.

将所有前缀和离散化,开两个树状数组进行维护,时间复杂度 $O(37\cdot n\log n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=1e5+10;
int n,a[MAXN];
struct FenwickTree
{
	int bit[MAXN];
#define lowbit(x) x&(-x)
	void add(int x)
	{
		for(;x<=n+1;x+=lowbit(x))
			bit[x]^=1;
	}
	int sum(int x)
	{
		int s=0;
		for(;x;x-=lowbit(x))
			s^=bit[x];
		return s;
	}
	int query(int l,int r)
	{
		return sum(r)^sum(l-1);
	}
	void reset()
	{
		memset(bit,0,sizeof bit);
	}
}T[2];
int mx;
void solve1()
{
	int tot[2];
	int ans=0;
	for(int k=0;(1<<k)<=mx;++k)
	{
		tot[0]=1,tot[1]=0;
		int sum=0;
		for(int i=1;i<=n;++i)
		{
			sum^=(a[i]>>k)&1;
			ans=add(ans,mul(1<<k,tot[sum^1]));
			++tot[sum];
		}
	}
	printf("%d ",ans);
}
ll s[MAXN],S;
int tot;
void solve2()
{
	ll t,sum,ans=0;
	for(int k=0;(1LL<<k)<=S;++k)
	{
		T[0].reset();
		T[1].reset();
		sum=tot=0;
		s[++tot]=sum&((1LL<<k)-1);
		for(int i=1;i<=n;++i)
		{
			sum+=a[i];
			s[++tot]=sum&((1LL<<k)-1);
		}
		sort(s+1,s+1+tot);
		tot=unique(s+1,s+1+tot)-s-1;
		sum=t=0;
		T[(sum>>k)&1].add(lower_bound(s+1,s+1+tot,sum&((1LL<<k)-1))-s);
		for(int i=1;i<=n;++i)
		{
			sum+=a[i];
			int id=(sum>>k)&1,p=lower_bound(s+1,s+1+tot,sum&((1LL<<k)-1))-s;
			t^=T[id].query(p+1,tot);
			t^=T[id^1].query(1,p);
			T[id].add(p);
		}
		ans+=t<<k;
	}
	printf("%lld\n",ans);
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		mx=max(mx,a[i]);
		S+=a[i];
	}
	solve1();
	solve2();
	return 0;
}