bzoj 5476 位运算

Posted on | Views:

树状数组.

  • 如果直接离散化 + 莫队,时间复杂度 $O(m\sqrt n)$ ,无法通过.
  • 如果在计算异或和时,一个数在区间内出现了 $k$ 次,使最后一次不计入贡献,那么就只算了 $k-1$ 次.
  • 这样得到的答案就是出现偶数次的数的异或和.
  • 将询问离线,并按照 $r$ 排序,于是可以从前往后一个个加入数.加入一个数 $a_i$ 后,就处理所有 $r=i$ 的询问.
  • 每次加入数 $x$ 时,在它的上一次出现的位置(若有)加入贡献即可.用树状数组维护前缀异或和.

$bzoj$ 上数据有点毒.还需要开 $long\ long$. 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll 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 MAXN=1e6+10;
ll a[MAXN],A[MAXN];
int n,m,tot;
ll res[MAXN];
struct qry
{
	int l,r;
	int id;
	bool operator < (const qry &rhs) const
	{
		return r==rhs.r?l<rhs.l:r<rhs.r;
	}
}q[MAXN];
#define lowbit(x) x&(-x)
ll bit[MAXN];
void add(int x,ll c)
{
	for(;x<=n;x+=lowbit(x))
		bit[x]^=c;
}
ll sum(int x)
{
	ll s=0;
	for(;x>0;x-=lowbit(x))
		s^=bit[x];
	return s;
}
ll query(int l,int r)
{
	return sum(r)^sum(l-1);
}
int lstpos[MAXN];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		A[i]=a[i]=read();
	sort(A+1,A+1+n);
	tot=unique(A+1,A+1+n)-A-1;
	m=read();
	for(int i=1;i<=m;++i)
	{
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+1+m);
	for(int i=1,j=1;i<=n;++i)
	{
		int x=lower_bound(A+1,A+1+tot,a[i])-A;
		if(lstpos[x])
			add(lstpos[x],A[x]);
		lstpos[x]=i;
		for(;j<=m && q[j].r==i;++j)
			res[q[j].id]=query(q[j].l,q[j].r);
	}
	for(int i=1;i<=m;++i)
		printf("%lld\n",res[i]);
	return 0;
}